时间复杂度（刘汝佳）（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石家庄)