时间复杂度_刘汝佳.ppt

ADT与时间复杂度 NOI培训 刘汝佳 储钱罐 有一只自动储钱罐 它有一个孔和一个按钮 存钱的时候 你可以从小孔往里面投一枚硬币 取钱的时候 只要按一下按钮 面值最大的硬币就会从孔里掉出来 我们不知道储钱罐里面有什么 不过这也没什么大不了的 因为我们知道它的使用方法 存钱和取钱并不需要了解储钱罐的机理抽象数据类型 ADT 小机器人 这个储钱罐的性能如何呢 也就是说 扔完一枚硬币以后需要多久才能扔第二枚硬币 按按钮多久后面值最大的硬币才会掉出来 自动储钱罐的设计者告诉你 钱罐里有一个很小的机器人 每次按下按钮的时候 它会从钱罐里找出最值钱的一枚 从孔里扔出来 那么小机器人的工作方式将直接影响到储钱罐的性能 ADT相同的数据结构 性能可能有差异 临时抱佛脚 小机器人是这样工作的 当你扔一枚硬币进来的时候 它什么都不做 自己睡大觉 当你按按钮的时候 它慌了 赶紧找钱 它先随便挑出一个硬币拿在手里 然后把其他所有硬币的看一遍 如果发现更值钱的 就用把手里的硬币换掉 最后手里拿着的就是最值钱的硬币 然后从孔里扔出去 分析 可以预料 这个钱罐 添加硬币 很快 小机器人啥都不做 找最大面值却很慢 如果小机器人检查一枚硬币的时间是0 01秒 那么有100个硬币时需要1秒 有10 000个硬币时需要100秒 约两分钟 而1 000 000个硬币时就需要10 000秒 约2 8小时 你可以忍受这样的速度吗 收银员 拿几个不同的小桶 每个桶装一种面值的硬币 假设一共有1元 5角 1角 5分 2分和1分共6种面值的硬币 则只需要六个桶 当来了一枚新硬币时 小机器人把它放到相应的盒子中 需要找钱时 小机器人只需要看1元的盒子里有没有硬币 有的话随便拿一个扔出去 如果没有的话再看5角的盒子有没有硬币 有的话随便拿一个扔出去 不管有多少硬币 只要盒子装得下 总是最多只需要开6次桶即可 即使每开一个桶需要5秒钟 有1 000 000个硬币时最多也只需要半分钟 比刚才的2 8小时快多了 可是 这个方法虽然好 但是前提是只有6种面值 如果1分 2分 3分 4分 99元9角8分 99元9角9分 100元整这1万种面值的硬币都有 那就需要1万个盒子 如果扔的1 000 000个硬币的面值全部不同 那么这个新方法就没有任何优势了 如果学过数据结构 事实上 存在一个更好的结构来实现这个储钱罐 它就是二叉堆实现法 不管面值有多少种 在有1 000 000个硬币的情况下也最多只需要不到一秒钟 储钱罐的ADT 储钱罐是一个优先队列 priorityqueue 每个硬币的优先级就是它的面值 每次优先级最大的出队 基本优先队列的操作如下 boolempty 判断队列是否为空voidinsert i p 加入一个元素i 优先级为pintgetmax 取得队列里最大元素并删除每次投入一枚面值相当于执行操作insert 按一次按钮相当于先执行empty 如果队列不空 则执行getmax 如何衡量时间性能 只能与算法相关 而不能受到硬件 代码实现的影响应尽量简单 抽象操作 对于单一操作的算法 我们有以下公式 运行时间 操作时间X操作次数操作时间取决于计算机 而操作次数取决于算法 在刚才的钱罐的例子中 拿硬币 打开盒子的时间取决于机器人的硬件 而需要拿多少个硬币 打开多少个盒子却只和算法有关 我们的目标是分析算法特性 估算出操作次数 这样 对于典型的计算机速度 我们也可以估算它执行某个程序的时间 对于同一台计算机 改变输入时估算它运行时间的变化 渐进时间复杂度 如果规模为n 程序一的操作数为3n 7 而程序二的操作数为10n2 5n 23 显然程序一比程序二好 对于一般情况 如何判断两个程序哪个更好呢 显然 可以先数出两个程序的操作数目 再加以比较 但是对于复杂的程序 很难写出完整的表达式 更别说比较了 在算法分析理论中 我们使用渐进的方法 先把操作数化成简单的形式 然后比较它们的阶 简化法则 简化的方法是 只保留最大项 忽略系数 比如程序一的3n 7化简后的结果为n 程序二为n2 而2n 7 10n50 987logn化简为2n 显然 这样化简忽略了很多因素 但是它保留最主要的项 方便比较 理论与现实 运行时间的影响因素 输入数据 最好 最坏 平均使用随机数 期望运行时间等 多项式时间和指数时间 很多时候算法分析不能做到十分精确 我们往往不说操作数等于多少 而只说操作数的上限是多少 我们用记号g n O f n 来表示当n充分大时 g n 不超过f n 的常数倍 如果f n 为多项式