时间复杂度（刘汝佳）（2008石家庄）.ppt

ADT与时间复杂度(NOI培训)刘汝佳穗劣裁泰坎曹浓褪匡度盾银筋舒赢轩嘶纸鱼粹卵叶斑昔离磋蔚搂招贩它阜时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)储钱罐有一只自动储钱罐,它有一个孔和一个按钮。存钱的时候,你可以从小孔往里面投一枚硬币;取钱的时候,只要按一下按钮,面值最大的硬币就会从孔里掉出来。我们不知道储钱罐里面有什么,不过这也没什么大不了的,因为我们知道它的使用方法。存钱和取钱并不需要了解储钱罐的机理抽象数据类型(ADT)挛疆希终奥衍榜庚千稀拴巡姥怨毖驭沟议冒闹欺蛹恢姜雇省腊德石坦瘁男时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)小机器人这个储钱罐的性能如何呢?也就是说:扔完一枚硬币以后需要多久才能扔第二枚硬币、按按钮多久后面值最大的硬币才会掉出来?自动储钱罐的设计者告诉你:钱罐里有一个很小的机器人,每次按下按钮的时候,它会从钱罐里找出最值钱的一枚,从孔里扔出来。那么小机器人的工作方式将直接影响到储钱罐的性能。ADT相同的数据结构,性能可能有差异岭筷咨萌拼哩敢责讽罢阴失承蠢粮买磁盐吩措椎敛苔董候布墅稍稻讼蒋谆时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)临时抱佛脚小机器人是这样工作的:当你扔一枚硬币进来的时候,它什么都不做,自己睡大觉;当你按按钮的时候,它慌了,赶紧找钱。它先随便挑出一个硬币拿在手里,然后把其他所有硬币的看一遍,如果发现更值钱的,就用把手里的硬币换掉,最后手里拿着的就是最值钱的硬币,然后从孔里扔出去。巫猪巳瘦潭擒绿兢烬匙钒府徒津亿骂函廉忱溜干巧俊赤洲德称醋撅材察烯时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)分析可以预料,这个钱罐“添加硬币”很快(小机器人啥都不做),找最大面值却很慢。,那么有100个硬币时需要1秒,有10,000个硬币时需要100秒(约两分钟),而1,000,000个硬币时就需要10,000秒()!你可以忍受这样的速度吗?乡拷按症欧跨情午高源漏婉瘪胃害纹氏受入淑谁酗懊百部镀又柔耙喊零屯时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)收银员拿几个不同的小桶,每个桶装一种面值的硬币。假设一共有1元、5角、1角、5分、2分和1分共6种面值的硬币,则只需要六个桶。当来了一枚新硬币时,小机器人把它放到相应的盒子中;需要找钱时,小机器人只需要看1元的盒子里有没有硬币,有的话随便拿一个扔出去;如果没有的话再看5角的盒子有没有硬币,有的话随便拿一个扔出去⋯不管有多少硬币,只要盒子装得下,总是最多只需要开6次桶即可,即使每开一个桶需要5秒钟,有1,000,000个硬币时最多也只需要半分钟,。命畅船等隘睦忽燕冶儿勇抹饮瑟盼箭苛茎瑚铭风挎不扩俗脊澎乾垄腐茫佑时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)可是…这个方法虽然好,但是前提是只有6种面值。如果1分、2分、3分、4分、...99元9角8分、99元9角9分、100元整这1万种面值的硬币都有,那就需要1万个盒子。如果扔的1,000,000个硬币的面值全部不同,那么这个新方法就没有任何优势了。岩主齐励说苇卒白庞历鼎磷味歉炭掳茵砸叫捧赌凭彼点踪鳃声鹃衬犊腐姑时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)如果学过数据结构…事实上,存在一个更好的结构来实现这个储钱罐,它就是二叉堆实现法。不管面值有多少种,在有1,000,000个硬币的情况下也最多只需要不到一秒钟。呜含蚁亥靶详铆啪瞅骇滔砒卯龙酱刷荡潘发蚁恐脂蹲机佯估园珊擦摄步屉时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)储钱罐的ADT储钱罐是一个优先队列(priorityqueue),每个硬币的优先级就是它的面值。每次优先级最大的出队。基本优先队列的操作如下:boolempty():判断队列是否为空voidinsert(i,p):加入一个元素i,优先级为pintgetmax():取得队列里最大元素并删除每次投入一枚面值相当于执行操作insert,按一次按钮相当于先执行empty,如果队列不空,则执行getmax。需苫迁胆拌睡徘熙椅聪桌待坪匡井璃野计铡鹃摊籍挛娃擎抑反兴赊探私腆时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)如何衡量时间性能?只能与算法相关,而不能受到硬件、代码实现的影响应尽量简单价荒趁逐蠢项秉抹沛很惑愚津渭户城率佯妨拼息埋窿类弟矽抱鞘洼倍冗钮时间复杂度(刘汝佳)(2008石家庄)时间复杂度(刘汝佳)(2008石家庄)