時(shí)間復(fù)雜度（劉汝佳）（2008石家莊）.ppt

1、ADT與時(shí)間復(fù)雜度(NOI培訓(xùn)),劉汝佳,儲(chǔ)錢(qián)罐,有一只自動(dòng)儲(chǔ)錢(qián)罐，它有一個(gè)孔和一個(gè)按鈕。存錢(qián)的時(shí)候，你可以從小孔往里面投一枚硬幣；取錢(qián)的時(shí)候，只要按一下按鈕，面值最大的硬幣就會(huì)從孔里掉出來(lái)。 我們不知道儲(chǔ)錢(qián)罐里面有什么，不過(guò)這也沒(méi)什么大不了的，因?yàn)槲覀冎浪氖褂梅椒ā４驽X(qián)和取錢(qián)并不需要了解儲(chǔ)錢(qián)罐的機(jī)理 抽象數(shù)據(jù)類(lèi)型(ADT),小機(jī)器人,這個(gè)儲(chǔ)錢(qián)罐的性能如何呢？也就是說(shuō)：扔完一枚硬幣以后需要多久才能扔第二枚硬幣、按按鈕多久后面值最大的硬幣才會(huì)掉出來(lái)？ 自動(dòng)儲(chǔ)錢(qián)罐的設(shè)計(jì)者告訴你：錢(qián)罐里有一個(gè)很小的機(jī)器人，每次按下按鈕的時(shí)候，它會(huì)從錢(qián)罐里找出最值錢(qián)的一枚，從孔里扔出來(lái)。那么小機(jī)器人的工作方式將直

2、接影響到儲(chǔ)錢(qián)罐的性能。 ADT相同的數(shù)據(jù)結(jié)構(gòu)，性能可能有差異,臨時(shí)抱佛腳,小機(jī)器人是這樣工作的：當(dāng)你扔一枚硬幣進(jìn)來(lái)的時(shí)候，它什么都不做，自己睡大覺(jué)； 當(dāng)你按按鈕的時(shí)候，它慌了，趕緊找錢(qián)。它先隨便挑出一個(gè)硬幣拿在手里，然后把其他所有硬幣的看一遍，如果發(fā)現(xiàn)更值錢(qián)的，就用把手里的硬幣換掉，最后手里拿著的就是最值錢(qián)的硬幣，然后從孔里扔出去。,分析,可以預(yù)料，這個(gè)錢(qián)罐“添加硬幣”很快（小機(jī)器人啥都不做），找最大面值卻很慢。 如果小機(jī)器人檢查一枚硬幣的時(shí)間是0.01秒，那么有100個(gè)硬幣時(shí)需要1秒，有10,000個(gè)硬幣時(shí)需要100秒（約兩分鐘），而1,000,000個(gè)硬幣時(shí)就需要10,000秒（約2.8小

3、時(shí)）！你可以忍受這樣的速度嗎？,收銀員,拿幾個(gè)不同的小桶，每個(gè)桶裝一種面值的硬幣。假設(shè)一共有1元、5角、1角、5分、2分和1分共6種面值的硬幣，則只需要六個(gè)桶。當(dāng)來(lái)了一枚新硬幣時(shí)，小機(jī)器人把它放到相應(yīng)的盒子中；需要找錢(qián)時(shí)，小機(jī)器人只需要看1元的盒子里有沒(méi)有硬幣，有的話隨便拿一個(gè)扔出去；如果沒(méi)有的話再看5角的盒子有沒(méi)有硬幣，有的話隨便拿一個(gè)扔出去不管有多少硬幣，只要盒子裝得下，總是最多只需要開(kāi)6次桶即可，即使每開(kāi)一個(gè)桶需要5秒鐘，有1,000,000個(gè)硬幣時(shí)最多也只需要半分鐘，比剛才的2.8小時(shí)快多了。,可是,這個(gè)方法雖然好，但是前提是只有6種面值。如果1分、2分、3分、4分、. . .99元9

4、角8分、99元9角9分、100元整這1萬(wàn)種面值的硬幣都有，那就需要1萬(wàn)個(gè)盒子。如果扔的1,000,000個(gè)硬幣的面值全部不同，那么這個(gè)新方法就沒(méi)有任何優(yōu)勢(shì)了。,如果學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu),事實(shí)上，存在一個(gè)更好的結(jié)構(gòu)來(lái)實(shí)現(xiàn)這個(gè)儲(chǔ)錢(qián)罐，它就是二叉堆實(shí)現(xiàn)法。不管面值有多少種，在有1,000,000個(gè)硬幣的情況下也最多只需要不到一秒鐘。,儲(chǔ)錢(qián)罐的ADT,儲(chǔ)錢(qián)罐是一個(gè)優(yōu)先隊(duì)列(priority queue) ，每個(gè)硬幣的優(yōu)先級(jí)就是它的面值。每次優(yōu)先級(jí)最大的出隊(duì)?；緝?yōu)先隊(duì)列的操作如下： bool empty()：判斷隊(duì)列是否為空 void insert(i, p)：加入一個(gè)元素i，優(yōu)先級(jí)為p int getmax

5、()：取得隊(duì)列里最大元素并刪除 每次投入一枚面值相當(dāng)于執(zhí)行操作insert，按一次按鈕相當(dāng)于先執(zhí)行empty，如果隊(duì)列不空，則執(zhí)行g(shù)etmax。,如何衡量時(shí)間性能？,只能與算法相關(guān)，而不能受到硬件、代碼實(shí)現(xiàn)的影響 應(yīng)盡量簡(jiǎn)單,抽象操作,對(duì)于單一操作的算法, 我們有以下公式： 運(yùn)行時(shí)間 = 操作時(shí)間 X 操作次數(shù) 操作時(shí)間取決于計(jì)算機(jī)，而操作次數(shù)取決于算法。在剛才的錢(qián)罐的例子中，拿硬幣、打開(kāi)盒子的時(shí)間取決于機(jī)器人的硬件，而需要拿多少個(gè)硬幣、打開(kāi)多少個(gè)盒子卻只和算法有關(guān)。 我們的目標(biāo)是分析算法特性, 估算出操作次數(shù)。這樣，對(duì)于典型的計(jì)算機(jī)速度，我們也可以估算它執(zhí)行某個(gè)程序的時(shí)間；對(duì)于同一臺(tái)計(jì)算機(jī)，

6、改變輸入時(shí)估算它運(yùn)行時(shí)間的變化。,漸進(jìn)時(shí)間復(fù)雜度,如果規(guī)模為n，程序一的操作數(shù)為3n + 7，而程序二的操作數(shù)為10n2 + 5n + 23，顯然程序一比程序二好。對(duì)于一般情況，如何判斷兩個(gè)程序哪個(gè)更好呢？顯然，可以先數(shù)出兩個(gè)程序的操作數(shù)目，再加以比較，但是對(duì)于復(fù)雜的程序，很難寫(xiě)出完整的表達(dá)式，更別說(shuō)比較了。在算法分析理論中，我們使用漸進(jìn)的方法，先把操作數(shù)化成簡(jiǎn)單的形式，然后比較它們的階。,簡(jiǎn)化法則,簡(jiǎn)化的方法是：只保留最大項(xiàng)，忽略系數(shù)。比如程序一的3n+7化簡(jiǎn)后的結(jié)果為n，程序二為n2，而2n+7 + 10n50 + 987 log n 化簡(jiǎn)為2n。 顯然，這樣化簡(jiǎn)忽略了很多因素，但是它保留最主要的項(xiàng)，方便比較。,理論與現(xiàn)實(shí),運(yùn)行時(shí)間的影響因素,輸入數(shù)據(jù)：最好、最壞、平均 使用隨機(jī)數(shù)：期望運(yùn)行時(shí)間等,多項(xiàng)式時(shí)間和指數(shù)時(shí)間,很多時(shí)候算法分析不能做到十分精確，我們往往不說(shuō)操作數(shù)等于多少，而只說(shuō)操作數(shù)的上限是多少，我們用記號(hào)g(n) = O(f(n)來(lái)表示當(dāng)n充分大時(shí)，g(n)不超過(guò)f(n)的常數(shù)倍。如果f(n)為多項(xiàng)式（如