成人国产精品视频,日韩av中文在线,在线黄色片视频,大香蕉伊人综合,一级A片在线免费,四色成人电影,狠狠操五月天,成人三级片在线免费观看

數(shù)學(xué)算法俱樂(lè)部

日期：2020年08月15日

正文共：12997字10圖

預(yù)計(jì)閱讀時(shí)間：33分鐘

來(lái)源：《真實(shí)世界的算法：初學(xué)者指南》

設(shè)想你可以獲得一只股票的每日?qǐng)?bào)價(jià)。也就是說(shuō)，你得到一個(gè)數(shù)值序列，每個(gè)數(shù)表示一只給定股票在某天的收盤(pán)價(jià)。這些收盤(pán)價(jià)已按時(shí)間順序排列好。股票市場(chǎng)關(guān)閉的日子沒(méi)有對(duì)應(yīng)的報(bào)價(jià)。

一只股票的價(jià)格在某天的跨度（span）是指這一天之前連續(xù)多少天股票價(jià)格低于或等于這天的價(jià)格。于是股票跨度問(wèn)題（Stock Span Problem）定義為，給定一只股票的每日?qǐng)?bào)價(jià)序列，對(duì)序列中每一天求出股票的跨度。例如，考慮圖1-1。我們的數(shù)據(jù)從第0天開(kāi)始，第6天的跨度為5天，第5天的跨度為4天，第4天的跨度為1天。

在現(xiàn)實(shí)中，股票每日?qǐng)?bào)價(jià)序列可能包含數(shù)千天的數(shù)據(jù)，而我們可能希望對(duì)很多不同的序列計(jì)算跨度，每個(gè)序列描述了一只不同的股票的價(jià)格演變。因此我們希望使用計(jì)算機(jī)求解此問(wèn)題。

對(duì)于很多用計(jì)算機(jī)來(lái)求解的問(wèn)題，通常都存在多種求解方法，其中一些方法比另外一些更好。這里，“更好”這個(gè)詞自身并沒(méi)有什么實(shí)際意義。當(dāng)我們說(shuō)更好時(shí)，實(shí)際是說(shuō)某些方面更好?？赡苁撬俣确矫?、內(nèi)存方面或是影響時(shí)間和空間等資源的其他方面。我們會(huì)對(duì)此進(jìn)行更多的討論，但重要的是從一開(kāi)始就要記住這一點(diǎn)，因?yàn)閱?wèn)題的一個(gè)解可能很簡(jiǎn)單但按照我們?cè)O(shè)置的一些約束或標(biāo)準(zhǔn)并不是最優(yōu)的。

假定你正在計(jì)算序列中第m天的股票跨度，一種方法是回退一天，這樣就處于第m-1天。如果第m-1天的價(jià)格大于第m天的價(jià)格，你就知道了第m天的股票跨度僅為1天。但如果第m-1天的價(jià)格小于或等于第m天的價(jià)格，則第m天的股票跨度至少為2天，也可能更大，取決于更早的股票價(jià)格是多少。因此我們繼續(xù)檢查第m-2天的價(jià)格。如果價(jià)格不大于第m天的價(jià)格，則檢查再前一天，依此類推。最終可能發(fā)生兩種情況：第一種情況是檢查完所有日期（即到達(dá)了序列的起點(diǎn)），也就是第m天之前的所有股票價(jià)格都小于或等于第m天，于是跨度恰為m天；第二種情況是檢查到第k（k＜m）天時(shí)，發(fā)現(xiàn)股票價(jià)格高于第m天，則跨度為m-k天。

如果序列包含n天的數(shù)據(jù)，則為了求解跨度問(wèn)題需要重復(fù)上述過(guò)程n次，每次計(jì)算出一天的跨度。你可以在圖1-1的例子上仔細(xì)驗(yàn)證此過(guò)程的正確性。

現(xiàn)在還有一個(gè)問(wèn)題，上面對(duì)求解過(guò)程的描述并不是一種非常好的方式。在這個(gè)世界上，散文是交流幾乎所有事情的極好方式，但提供給計(jì)算機(jī)的過(guò)程除外，因?yàn)樵诿枋鎏峁┙o計(jì)算機(jī)的東西時(shí)，必須十分精確。

如果我們的描述足夠精確，計(jì)算機(jī)能夠理解我們的過(guò)程，就意味著我們已經(jīng)創(chuàng)建了一個(gè)程序（program）。但用計(jì)算機(jī)程序來(lái)描述一個(gè)過(guò)程可能又并非易于人類理解的最佳方式，因?yàn)槟惚仨毟嬖V計(jì)算機(jī)要做的所有細(xì)節(jié)，而且是以計(jì)算機(jī)的工作方式告訴它，而這些不一定與問(wèn)題的解相關(guān)。一個(gè)描述如果足夠詳細(xì)、可被計(jì)算機(jī)理解，對(duì)于人類來(lái)說(shuō)可能就過(guò)于詳細(xì)而難于理解了。

因此我們可以做一下權(quán)衡，通過(guò)某種比簡(jiǎn)單文本更精確的結(jié)構(gòu)化語(yǔ)言來(lái)描述求解過(guò)程，而且人類理解它也沒(méi)有什么困難。這種結(jié)構(gòu)化語(yǔ)言不一定能被計(jì)算機(jī)直接執(zhí)行，但可以簡(jiǎn)單地轉(zhuǎn)換為真正的計(jì)算機(jī)程序。

1.1算法

在求解股票跨度問(wèn)題之前，你最好熟悉一個(gè)重要的術(shù)語(yǔ)。算法（algorithm）就是一個(gè)過(guò)程，是一種特殊的過(guò)程。它必須描述為一個(gè)有限步驟序列，且必須在有限時(shí)間內(nèi)結(jié)束。每個(gè)步驟必須是良好定義的，達(dá)到人類可用一支筆和一張紙執(zhí)行它的程度。算法基于我們提供給它的輸入做一些事情，并生成反映其所做工作的一些輸出。算法1-1實(shí)現(xiàn)了我們前面描述的過(guò)程。

算法1-1展示了如何描述算法。我們并不使用某種計(jì)算機(jī)語(yǔ)言，因?yàn)槟菢訒?huì)迫使我們處理與算法邏輯無(wú)關(guān)的實(shí)現(xiàn)細(xì)節(jié)，我們使用的是某種偽代碼（pseudocode）形式。偽代碼是一種介于真正的程序代碼和非形式化描述之間的形式。它使用一種結(jié)構(gòu)化格式，并采用一組具有特定含義的詞匯。但是，偽代碼不是真正的計(jì)算機(jī)代碼。它并不是為了被計(jì)算機(jī)執(zhí)行，而是易于被人類理解。順便提一下，程序也應(yīng)能被人類理解，但并非所有程序都是如此——有很多正在運(yùn)行的計(jì)算機(jī)程序?qū)懙煤茉愀?，難以理解。

每個(gè)算法都有一個(gè)名字，接受一些輸入，并生成一些輸出。在本書(shū)中，算法的名字將采用駱駝拼寫(xiě)法（CamelCase），輸入會(huì)寫(xiě)在括號(hào)中，輸出用一個(gè)→指示。接下來(lái)的幾行將會(huì)對(duì)算法的輸入和輸出進(jìn)行描述?？梢杂盟惴ǖ拿志o接放在括號(hào)中的輸入來(lái)調(diào)用（call）算法。一旦算法編寫(xiě)好，就可以將其作為一個(gè)黑盒來(lái)處理，可以給它一些輸入，黑盒則會(huì)返回算法的輸出。當(dāng)用一種程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)一個(gè)算法時(shí)，它就是一個(gè)具名的計(jì)算機(jī)代碼片段——函數(shù)（function）。在一個(gè)計(jì)算機(jī)程序中，我們調(diào)用實(shí)現(xiàn)算法的函數(shù)。

某些算法不生成輸出，當(dāng)然也就不會(huì)顯式返回結(jié)果。取而代之的是，它們的行為影響上下文的某部分。例如，我們可能提供給算法一個(gè)空間，供其寫(xiě)入結(jié)果。在此情況下，在傳統(tǒng)意義上算法并非返回輸出結(jié)果，但無(wú)論如何算法是有輸出的，即它影響上下文發(fā)生的變化。某些程序設(shè)計(jì)語(yǔ)言會(huì)區(qū)分顯式返回結(jié)果的具名程序代碼片段——稱為函數(shù)（function），以及不返回結(jié)果但可能有其他副作用的具名程序代碼片段——稱為過(guò)程（procedure）。這種差異來(lái)源于數(shù)學(xué)，數(shù)學(xué)上的函數(shù)是必須返回值的。對(duì)我們來(lái)說(shuō)，當(dāng)一個(gè)算法編碼為實(shí)際程序時(shí)，既可以是一個(gè)函數(shù)也可以是一個(gè)過(guò)程。

我們的偽代碼中使用一些用粗體表示的關(guān)鍵字，如果你對(duì)計(jì)算機(jī)和程序設(shè)計(jì)語(yǔ)言的工作方式有所了解，這些關(guān)鍵字的含義就是不言自明的了。我們使用字符←表示賦值，用等號(hào)（=）表示相等比較。我們采用常用的五個(gè)符號(hào)（+，-，/，×，·）表示四種數(shù)學(xué)運(yùn)算，后兩個(gè)符號(hào)都表示乘法，這兩個(gè)符號(hào)我們都會(huì)使用，基于美學(xué)考慮進(jìn)行選擇。我們將不會(huì)使用任何關(guān)鍵字或符號(hào)對(duì)偽代碼分塊，分塊是通過(guò)縮進(jìn)來(lái)表示的。

在這個(gè)算法中，我們使用了數(shù)組（array）。數(shù)組是一種保存數(shù)據(jù)的結(jié)構(gòu)，它允許我們按特定方式操縱其中的數(shù)據(jù)。我們保存數(shù)據(jù)并允許在其保存的數(shù)據(jù)上執(zhí)行特定操作的結(jié)構(gòu)稱為數(shù)據(jù)結(jié)構(gòu)（data structure）。因此數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)。

數(shù)組之于計(jì)算機(jī)，就像對(duì)象序列之于人類。數(shù)組是元素的有序序列，這些元素存儲(chǔ)在計(jì)算機(jī)內(nèi)存中。為了獲得保存元素所需的空間并創(chuàng)建一個(gè)保存n個(gè)元素的數(shù)組，可調(diào)用算法1-1第1行中的CreateArray算法。如果你熟悉數(shù)組，可能就會(huì)奇怪創(chuàng)建數(shù)組怎么還需要一個(gè)算法。但實(shí)際情況的確如此。為了獲得保存數(shù)據(jù)的一塊內(nèi)存，你必須至少在計(jì)算機(jī)中搜索可用內(nèi)存并標(biāo)記它為數(shù)組所用。CreateArray(n)調(diào)用做了所需的一切，它返回一個(gè)可容納n個(gè)元素的數(shù)組，初始時(shí)其中沒(méi)有元素，只有保存元素所需的空間。算法負(fù)責(zé)調(diào)用CreateArray(n)來(lái)將實(shí)際數(shù)據(jù)填充到數(shù)組中。

對(duì)數(shù)組A，我們用A[i]表示其第i個(gè)元素，訪問(wèn)該元素也是用該符號(hào)。一個(gè)元素在數(shù)組中的位置，如A[i]中的i，被稱為索引（index）。一個(gè)n個(gè)元素的數(shù)組A包含元素A[0]，A[1]，…，A[n-1]。這可能令你吃驚，因?yàn)槠涫自厥堑?個(gè)，而尾元素是第n-1個(gè)，可能你的預(yù)期是第1個(gè)和第n個(gè)。但是，大多數(shù)計(jì)算機(jī)語(yǔ)言中的數(shù)組都是如此，你最好現(xiàn)在就熟悉這種機(jī)制。這非常常見(jiàn)，當(dāng)遍歷一個(gè)大小為n的數(shù)組時(shí)，我們是從位置0遍歷到位置n-1。在我們的算法中，當(dāng)我們說(shuō)某個(gè)對(duì)象的取值是從數(shù)x到數(shù)y（假定x小于y）時(shí)，意思是從x到y(tǒng)（但不包含）的所有值，參見(jiàn)算法第2行。

我們假定無(wú)論i的值是什么，訪問(wèn)第i個(gè)元素都花費(fèi)相同的時(shí)間。因此訪問(wèn)A[0]與訪問(wèn)A[n-1]需要相同的時(shí)間。這是數(shù)組的一個(gè)非常重要的特性：對(duì)元素的訪問(wèn)是一致的，都花費(fèi)常量時(shí)間。當(dāng)我們通過(guò)索引訪問(wèn)數(shù)組元素時(shí)，數(shù)組不需要搜索此元素。

關(guān)于算法描述中的符號(hào)表示，我們用小寫(xiě)字母表示算法中的變量。但當(dāng)變量表示一個(gè)數(shù)據(jù)結(jié)構(gòu)時(shí)，我們會(huì)使用大寫(xiě)字母來(lái)令其突出，如數(shù)組A。但這并非必要。當(dāng)我們希望給變量起一個(gè)包含很多單詞的名字時(shí)，我們會(huì)使用下劃線（_），如a_connector。這是必要的，因?yàn)橛?jì)算機(jī)不理解由一組空格分隔的單詞構(gòu)成單個(gè)變量名的方式。

算法1-1使用數(shù)組保存數(shù)值。數(shù)組可以保存任何類型的項(xiàng)，在我們的偽代碼中每個(gè)數(shù)組只能保存單一類型的項(xiàng)。大多數(shù)程序設(shè)計(jì)語(yǔ)言中也都是如此。例如，可以創(chuàng)建十進(jìn)制數(shù)數(shù)組、分?jǐn)?shù)數(shù)組、表示人的項(xiàng)的數(shù)組以及另一個(gè)表示地址的項(xiàng)的數(shù)組，但不可以創(chuàng)建一個(gè)既包含十進(jìn)制數(shù)又包含表示人的項(xiàng)的數(shù)組。至于“表示人的項(xiàng)”會(huì)是什么，由編程所使用的語(yǔ)言所決定。所有程序設(shè)計(jì)語(yǔ)言都提供表示有意義的東西的方法。

一種特別有用的數(shù)組是字符數(shù)組。一個(gè)字符數(shù)組表示一個(gè)字符串（string），即一個(gè)字母序列、一個(gè)數(shù)序列、一個(gè)單詞序列、一個(gè)句子序列等。與所有數(shù)組一樣，我們可以用索引單獨(dú)引用數(shù)組中的單個(gè)字符。如果我們有一個(gè)字符串s=“Hello，World”，則s[0]為字母“H”而s[11]為字母“d”。

總結(jié)一下，數(shù)組就是一個(gè)保存相同類型項(xiàng)的序列的數(shù)據(jù)結(jié)構(gòu)。數(shù)組支持兩種操作：

? CreateArray(n)創(chuàng)建一個(gè)能保存n個(gè)元素的數(shù)組。數(shù)組未初始化，即它不保存任何實(shí)際元素，但保存元素所需的空間已預(yù)留，可用來(lái)保存元素。

? 正如我們已經(jīng)看到的，對(duì)一個(gè)數(shù)組A，A[i]訪問(wèn)其第i個(gè)元素，而且訪問(wèn)數(shù)組中任何元素都花費(fèi)相同時(shí)間。若i＜0，則試圖訪問(wèn)A[i]會(huì)產(chǎn)生錯(cuò)誤。

我們回到算法1-1。如前所述，算法第2～10行是一個(gè)循環(huán)，即一個(gè)反復(fù)執(zhí)行的代碼塊。如果我們有n天的報(bào)價(jià)的話，循環(huán)執(zhí)行n次，每次計(jì)算一個(gè)跨度。變量i表示我們正在計(jì)算跨度的當(dāng)前這一天。初始時(shí)，處于第0天這一最早的時(shí)間點(diǎn)。每次執(zhí)行第2行代碼時(shí)，就會(huì)推進(jìn)循環(huán)到第1，2，…，n-1天。

我們使用變量（variable）k指示當(dāng)前跨度的長(zhǎng)度——在我們的偽代碼中，變量就是一個(gè)引用某些數(shù)據(jù)的名字，那些數(shù)據(jù)的內(nèi)容，或者更精確地說(shuō)，變量的值（value），在算法執(zhí)行的過(guò)程中是可以改變的，變量這個(gè)術(shù)語(yǔ)因而得名。當(dāng)我們開(kāi)始計(jì)算一個(gè)跨度時(shí)，k的值總是1，我們是在第3行設(shè)置這個(gè)初值的。我們還使用了一個(gè)指示變量（indicator variable）span_end。指示變量取值TRUE或FALSE，指出某事成立或不成立。當(dāng)我們到達(dá)一個(gè)跨度的末端時(shí)，變量span_end的值將為真。

在開(kāi)始計(jì)算每個(gè)跨度時(shí)，span_end為假，如第4行所示。第5～9行的內(nèi)層循環(huán)計(jì)算跨度的長(zhǎng)度。第5行告訴我們，只要跨度還未結(jié)束，就回退盡可能長(zhǎng)的時(shí)間。我們能回退多遠(yuǎn)由條件i-k≥0決定：回退到索引i-k指示的這一天檢查跨度是否結(jié)束，而索引不能為0，因?yàn)?對(duì)應(yīng)第1天。第6行檢查跨度是否結(jié)束。如果跨度未結(jié)束，則在第7行增加其長(zhǎng)度。否則，我們注意到，第9行設(shè)置跨度結(jié)束，從而循環(huán)會(huì)在回到第5行后終止。第2～10行的外層循環(huán)在第10行結(jié)束一次循環(huán)時(shí)，我們?cè)诖藢的值保存到數(shù)組spans的正確位置。在退出循環(huán)后的第11行，我們返回spans，它保存著算法的結(jié)果。

注意，初始時(shí)我們?cè)O(shè)定i=0和k=1。這意味著在最早的時(shí)刻第5行的條件必定為假。這是理所應(yīng)當(dāng)?shù)?，因?yàn)榈?天的跨度只能為1。

此時(shí)此刻，記住我們?cè)f(shuō)過(guò)的關(guān)于算法、筆和紙的內(nèi)容。理解一個(gè)算法的最好方法就是去手動(dòng)執(zhí)行它。在任何時(shí)候如果一個(gè)算法看起來(lái)有些復(fù)雜，或者你不確定是否已完全理解它，就用紙和筆寫(xiě)下執(zhí)行它求解某個(gè)例子的過(guò)程。這種方法會(huì)節(jié)省你很多時(shí)間，雖然它看起來(lái)有點(diǎn)老套。如果對(duì)算法1-1還有不明確的地方，馬上嘗試這種方法，當(dāng)算法已完全清晰后再回到這里。

1.2運(yùn)行時(shí)間和復(fù)雜度

算法1-1給出了股票跨度問(wèn)題的一種解決方案，但我們可以做得更好。在這里，更好的意思是可以做得更快。當(dāng)討論算法的速度時(shí)，實(shí)際上討論的是算法執(zhí)行的步驟數(shù)。不管計(jì)算機(jī)變得多么快，即使計(jì)算步驟的執(zhí)行越來(lái)越快，步驟數(shù)也是保持不變的，因此用算法所需的步驟數(shù)來(lái)評(píng)價(jià)算法的性能就是很合理的了。我們稱步驟數(shù)為算法的運(yùn)行時(shí)間（running time），它是一個(gè)純數(shù)，不以任何時(shí)間單位來(lái)度量。使用時(shí)間單位會(huì)令運(yùn)行時(shí)間的任何評(píng)價(jià)都與特定的計(jì)算機(jī)模型關(guān)聯(lián)，從而降低其實(shí)用性。

我們來(lái)分析計(jì)算n只股票報(bào)價(jià)的跨度花費(fèi)多長(zhǎng)時(shí)間。算法由開(kāi)始于第2行的循環(huán)構(gòu)成，循環(huán)會(huì)執(zhí)行n次，每次計(jì)算一個(gè)報(bào)價(jià)。然后是從第5行開(kāi)始的內(nèi)層循環(huán)，外層循環(huán)每次會(huì)執(zhí)行此內(nèi)層循環(huán)來(lái)計(jì)算對(duì)應(yīng)股票報(bào)價(jià)的跨度。對(duì)每個(gè)報(bào)價(jià)，內(nèi)層循環(huán)會(huì)將它與之前的所有報(bào)價(jià)進(jìn)行比較。在最壞情況下，如果當(dāng)前報(bào)價(jià)是最高的，則會(huì)檢查之前所有的報(bào)價(jià)。如果第k個(gè)報(bào)價(jià)是之前所有報(bào)價(jià)中最高的，則內(nèi)層循環(huán)會(huì)執(zhí)行k次。因此，最壞情況下，即報(bào)價(jià)是降序排列的情況下，第6～7行會(huì)執(zhí)行這么多次：

如果你覺(jué)得等式不是那么清晰，可以將1，2，…，n這些數(shù)都累加兩次，這樣就能容易地看出結(jié)果的確如此：

由于第6～7行是算法運(yùn)行最多次的步驟，因此n(n-1)/2是算法最壞情況下的運(yùn)行時(shí)間。

當(dāng)我們討論算法的運(yùn)行時(shí)間時(shí)，真正感興趣的實(shí)際上是輸入數(shù)據(jù)很大（在我們的例子中，是數(shù)n很大）時(shí)的運(yùn)行時(shí)間。這就是算法的漸近（asymptotic）運(yùn)行時(shí)間，如此命名的原因是它刻畫(huà)的是輸入數(shù)據(jù)無(wú)限增大時(shí)算法的行為。為了描述漸近運(yùn)行時(shí)間，我們使用一些特殊符號(hào)。對(duì)任意函數(shù)f(n)，如果n大于某個(gè)初始正值時(shí)函數(shù)f(n)小于或等于另一個(gè)函數(shù)g(n)（用某個(gè)正的常數(shù)c縮放，即cg(n)），我們就稱O(f(n))=g(n)。更精確地，如果存在正常數(shù)c和n0使得0≤f(n)≤cg(n)對(duì)所有n≥n0成立，則我們稱O(f(n))=g(n)。

符號(hào)O(f(n))被稱為“大O符號(hào)”。記住，我們感興趣的是大規(guī)模的輸入，因?yàn)槟鞘菚?huì)節(jié)省最多時(shí)間的情況?？匆幌聢D1-2，其中我們繪制了兩個(gè)函數(shù)f1(n)=20n+1000和f2(n)=n2。對(duì)較小的n，f1(n)的值更大，但情況很快就發(fā)生了巨大變化，n2的增長(zhǎng)速度要快得多。

大O符號(hào)令我們可以簡(jiǎn)化復(fù)雜度描述中的函數(shù)。如果我們有一個(gè)像f(n)=3n3+5n2+2n+

1 000這樣的函數(shù)，則可以簡(jiǎn)化表示為O(f(n))=n3。為什么可以這樣？因?yàn)槲覀兛偸强梢哉业揭粋€(gè)值c使得0≤f(n)≤cn3。一般而言，當(dāng)我們有一個(gè)包含多項(xiàng)的函數(shù)時(shí)，其最大項(xiàng)會(huì)很快主導(dǎo)函數(shù)的增長(zhǎng)，因此可以去掉最小的那些項(xiàng)，使用大O符號(hào)。因此O(a1nk+a2nk-1 +…+akn+b)=O(nk)。

這種描述算法運(yùn)行時(shí)間的方式通常被稱為算法的計(jì)算復(fù)雜度（computational complexity），或簡(jiǎn)稱為復(fù)雜度（complexity）。我們研究算法運(yùn)行時(shí)間時(shí)使用簡(jiǎn)化形式的函數(shù)，而研究表明，大多數(shù)算法的運(yùn)行時(shí)間的確可以用少數(shù)簡(jiǎn)化函數(shù)之一描述。這意味著算法的復(fù)雜度通常可被歸為少數(shù)常見(jiàn)類別之一。

首先是常量函數(shù)（constant function）f(n)=c。這就意味著無(wú)論n的值是什么，函數(shù)總是具有相同的值c。除非c的值高得離譜，否則這是我們希望一個(gè)算法能達(dá)到的最佳復(fù)雜度。用大O符號(hào)表示的話，根據(jù)定義，我們有正常數(shù)c和n0使得0≤f(n)≤cg(n)=c·1。實(shí)際上，c就是函數(shù)的常數(shù)值，而n0=1。因此，O(c)=O(1)。如果算法有這樣的行為，我們稱其為常量時(shí)間算法（constant time algorithm）。這實(shí)際上是用詞不當(dāng)，因?yàn)槌Ａ繒r(shí)間并不意味著無(wú)論給算法什么輸入它都會(huì)花相同的時(shí)間。其準(zhǔn)確含義是算法運(yùn)行時(shí)間的上界與其輸入無(wú)關(guān)。例如，一個(gè)簡(jiǎn)單的算法實(shí)現(xiàn)x＞0時(shí)將y的值加到x的值上，它就不總是花費(fèi)相同的運(yùn)行時(shí)間：若x＞0，它執(zhí)行一次加法，否則什么也不做。但其上界是常數(shù)，即加法花費(fèi)的時(shí)間，因此它應(yīng)歸入O(1)類。遺憾的是，常量時(shí)間的算法并不多。最常見(jiàn)的常量時(shí)間的操作是訪問(wèn)數(shù)組中的元素，其花費(fèi)的時(shí)間是常數(shù)，不依賴于我們要訪問(wèn)的元素的索引。如我們已見(jiàn)到的，在一個(gè)包含n個(gè)元素的數(shù)組A中，訪問(wèn)A[0]和訪問(wèn)A[n-1]花費(fèi)相同的時(shí)間。

在常量時(shí)間算法之后，就是對(duì)數(shù)時(shí)間（logarithmic time）算法了。對(duì)數(shù)函數(shù)或稱對(duì)數(shù)（logarithm）為loga(n)，其定義是為了得到n而對(duì)a施加的冪次：若y=loga(n)，則n=ay。數(shù)a稱為對(duì)數(shù)的底（base of the logarithm）。從對(duì)數(shù)的定義可知x=alogax，這表明對(duì)數(shù)是指數(shù)的逆。實(shí)際上，log327=3，而33=27。若a=10，即對(duì)數(shù)以10為底，則可簡(jiǎn)寫(xiě)為y=log(n)。在計(jì)算機(jī)中我們經(jīng)常遇到以2為底的對(duì)數(shù)（base two logarithm），稱為二進(jìn)制對(duì)數(shù)，因此我們使用一個(gè)特殊的符號(hào)lg(n)=log2(n)來(lái)表示這種對(duì)數(shù)。這不同于所謂的自然對(duì)數(shù)（natural logarithm），即以e≈2.718 28為底的對(duì)數(shù)。自然對(duì)數(shù)也有其特殊符號(hào)表示：ln(n)=loge(n)。

數(shù)e有時(shí)也被稱為歐拉數(shù)，因18世紀(jì)瑞士數(shù)學(xué)家萊昂哈德·歐拉而得名，它出現(xiàn)在很多不同領(lǐng)域中。它是n趨向于無(wú)窮時(shí)表達(dá)式(1+1/n)n的極限。雖然得名于歐拉，但它實(shí)際上是另一位生活在17世紀(jì)的瑞士數(shù)學(xué)家雅各比·伯努利發(fā)現(xiàn)的，伯努利當(dāng)時(shí)正嘗試提出一個(gè)計(jì)算連續(xù)利息的公式。

設(shè)想你將d美元存入銀行，銀行給你的利率是R%。如果利息是每年計(jì)算一次，則一年之后你的存款將增長(zhǎng)到d+d(R/100)。設(shè)r=R/100，則你的存款是d(1+r)。你可以驗(yàn)證一下，如果R=50，r=1/2，你的存款將增長(zhǎng)到1.5×d。如果利息每年計(jì)算兩次，則每六個(gè)月的利率為r/2。六個(gè)月后你的存款為d(1+r/2)。再經(jīng)過(guò)六個(gè)月，在年底的時(shí)候，你的存款為d(1+r/2)(1+r/2)=d(1+r/2)2。如果每年施行利息（或用專業(yè)術(shù)語(yǔ)說(shuō)，復(fù)利計(jì)算）n次，則到年底你的存款變?yōu)閐(1+r/n)n。對(duì)R=100%這樣一個(gè)高利率，有r=1。如果按連續(xù)復(fù)利收益計(jì)算，即采用更小的時(shí)間間隔，n趨向于無(wú)窮的話，則當(dāng)d=1時(shí)，到年底你的存款將增長(zhǎng)到d(1+r/n)n=e。關(guān)于e的介紹就到這里。

對(duì)數(shù)的一個(gè)基本性質(zhì)是不同底的對(duì)數(shù)只差一個(gè)常數(shù)系數(shù)，這是因?yàn)閘oga(n)=logb(n)/logb(a)。例如，lg(n)=log10(n)/log10(2)。因此，雖然更特殊的O(lg(n))用得更多一些，但是我們將所有對(duì)數(shù)函數(shù)捆綁在相同的復(fù)雜度類別下，通常將其表示為O(log(n))。O(lg(n))復(fù)雜度的算法通常是反復(fù)將問(wèn)題一分為二的算法，因?yàn)槿绻惴磸?fù)將某個(gè)東西一分為二，本質(zhì)上就是在對(duì)它應(yīng)用對(duì)數(shù)函數(shù)。重要的對(duì)數(shù)時(shí)間算法都與搜索相關(guān)：最快的搜索算法的運(yùn)行時(shí)間是以2為底的對(duì)數(shù)。

比對(duì)數(shù)時(shí)間算法更耗時(shí)的就是線性時(shí)間算法（linear time algorithm）了，其運(yùn)行時(shí)間為f(n)=n，即時(shí)間與其輸入成比例。對(duì)這些算法，復(fù)雜度描述為O(n)。這樣的算法可能是掃描其整個(gè)輸入來(lái)尋找答案。例如，如果我們搜索一個(gè)未經(jīng)任何方式排序的項(xiàng)的隨機(jī)集合，則可能不得不遍歷所有項(xiàng)來(lái)找到我們想要的東西。因此，進(jìn)行這樣一次搜索的運(yùn)行時(shí)間是線性的。

比線性時(shí)間更慢的是對(duì)數(shù)線性時(shí)間算法（loglinear time algorithm），其中f(n)=nlog(n)，因此復(fù)雜度描述為O(nlog(n))。雖然實(shí)際算法中以2為底最為常見(jiàn)，但是對(duì)數(shù)依舊可以是任意的底。這些算法某種程度上是線性時(shí)間算法和對(duì)數(shù)時(shí)間算法的組合，可能包含反復(fù)劃分問(wèn)題的步驟及對(duì)劃分開(kāi)的每個(gè)部分應(yīng)用線性時(shí)間算法的步驟。好的排序算法具有對(duì)數(shù)線性時(shí)間復(fù)雜度。

如我們已經(jīng)看到的，當(dāng)描述算法運(yùn)行時(shí)間的函數(shù)是一個(gè)多項(xiàng)式f(n)=a1nk+a2nk-1+…+akn+b時(shí)，我們有復(fù)雜度O(nk)，算法稱為多項(xiàng)式時(shí)間算法（polynomial time algorithm）。很多算法是多項(xiàng)式時(shí)間的。一個(gè)很重要的子類別是O(n2)時(shí)間的算法，我們稱其為平方時(shí)間算法（quadratic time algorithm）。一些效率不高的排序算法就是平方時(shí)間的，將兩個(gè)n位數(shù)字的數(shù)相乘的標(biāo)準(zhǔn)算法也是平方時(shí)間的——注意，實(shí)際上更高效的乘法算法是存在的，在需要高性能算術(shù)計(jì)算的應(yīng)用中我們就會(huì)使用這些高效方法。

比多項(xiàng)式時(shí)間算法更慢的是指數(shù)時(shí)間算法（exponential time algorithm），其中f(n)=cn，c是一個(gè)常數(shù)值，因此大O符號(hào)表示為O(cn)。務(wù)必注意nc和cn的差別。雖然只是交換了n和指數(shù)的位置，但導(dǎo)致了函數(shù)間的巨大差異。如前所述，冪運(yùn)算是對(duì)數(shù)函數(shù)的逆，它簡(jiǎn)單地取一個(gè)常數(shù)的變量次冪。要小心：冪運(yùn)算是cn。指數(shù)函數(shù)（exponential function）是c=e時(shí)的特例，即f(n)=en，其中e是前面提到的歐拉數(shù)。指數(shù)時(shí)間產(chǎn)生的情況是，我們需要處理一個(gè)輸入規(guī)模為n的問(wèn)題，其中每個(gè)輸入都會(huì)取c個(gè)不同的值，而我們必須嘗試所有可能情況：對(duì)第一個(gè)輸入有c種取值，對(duì)其中每個(gè)值，都要考慮第二個(gè)輸入的c個(gè)值，共c×c=c2種情況；對(duì)這c2種情況中的每一種，都要考慮第三個(gè)輸入的c個(gè)可能值，使得總情況數(shù)變?yōu)閏2×c=c3；依此類推，直到最后一個(gè)輸入，總情況數(shù)變?yōu)閏n。

比指數(shù)時(shí)間算法還慢的是階乘時(shí)間算法（factorial time algorithm）O(n!)，其中階乘數(shù)定義為n!=1×2×…×n，退化情況為0!=1。當(dāng)求解一個(gè)問(wèn)題，需要嘗試輸入的所有可能排列（permutation）時(shí)，就會(huì)產(chǎn)生階乘時(shí)間。對(duì)于一個(gè)值的序列，它的一個(gè)排列就是值的順序的一個(gè)不同的安排。例如，如果有值[1，2，3]，則有如下排列：[1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]和[3，2，1]。在第一個(gè)位置上有n個(gè)可能的值。由于我們已經(jīng)用了一個(gè)值，因此在第二個(gè)位置上有n-1個(gè)可能值，前兩個(gè)位置的不同排列共有n×(n-1)種。對(duì)剩余位置我們像這樣繼續(xù)下去，直到在最后一個(gè)位置上只有一個(gè)可能值。因此，總共有n×(n-1)×…×1=n!種情況。階乘數(shù)也出現(xiàn)在洗牌中：一副撲克牌可能的洗牌數(shù)有52!種，這是一個(gè)天文數(shù)字。

經(jīng)驗(yàn)法則是，一個(gè)好的算法其時(shí)間復(fù)雜度最大是多項(xiàng)式的，因此我們的挑戰(zhàn)通常是尋找具有這樣性能的算法。遺憾的是，對(duì)于一大類重要的問(wèn)題，我們知道它們沒(méi)有多項(xiàng)式時(shí)間算法！看一下表1-1，你應(yīng)該認(rèn)識(shí)到，如果對(duì)一個(gè)問(wèn)題我們只有一個(gè)運(yùn)行時(shí)間為O(2n)的算法，則除了對(duì)一些簡(jiǎn)單問(wèn)題或很小規(guī)模的輸入外，該算法幾乎毫無(wú)價(jià)值。你可以通過(guò)圖1-3驗(yàn)證這一點(diǎn)：在最后一行，對(duì)較小的n值，O(2n)和O(n!)開(kāi)始飛漲。

在圖1-3中，顯示了針對(duì)幾個(gè)函數(shù)繪制的曲線，而實(shí)際上我們?cè)谘芯克惴〞r(shí)n都是自然數(shù)，因此我們預(yù)期看到的是顯示點(diǎn)而非線的散點(diǎn)圖。對(duì)數(shù)、線性、對(duì)數(shù)線性和多項(xiàng)式函數(shù)當(dāng)然都是直接對(duì)實(shí)數(shù)定義的，因此使用正常的函數(shù)定義繪制它們的曲線沒(méi)有什么問(wèn)題。冪運(yùn)算的解釋通常是針對(duì)整數(shù)的，但有理數(shù)指數(shù)的冪也是可能的，因?yàn)閤a/b=(xa)1/b= ?。于是實(shí)數(shù)指數(shù)的冪定義為bx=(elnb)x=exlnb。至于階乘，用一些更高等的數(shù)學(xué)知識(shí)，已證明可對(duì)所有實(shí)數(shù)定義（負(fù)階乘被當(dāng)作無(wú)窮）。因此我們將復(fù)雜度函數(shù)繪制為曲線是合理的。

為避免你認(rèn)為O(2n)或O(n!)的復(fù)雜度在實(shí)際中很少出現(xiàn)，請(qǐng)考慮著名的旅行商問(wèn)題。在這個(gè)問(wèn)題中，一個(gè)旅行商必須訪問(wèn)一些城市，每個(gè)城市只能訪問(wèn)一次。每個(gè)城市都直接連接著其他每個(gè)城市（可能旅行商是乘飛機(jī)旅行）。難點(diǎn)在于旅行商在完成這一目標(biāo)的同時(shí)還要經(jīng)過(guò)的公里數(shù)盡量少。一個(gè)直接的求解方案是嘗試這些城市所有可能的排列。對(duì)于n個(gè)城市，復(fù)雜度為O(n!)。存在一個(gè)求解此問(wèn)題的更好算法，復(fù)雜度為O(n22n)——只好一點(diǎn)點(diǎn)，在實(shí)際應(yīng)用中沒(méi)有很大差別。那么，我們?cè)撊绾谓鉀Q此問(wèn)題（以及其他類似問(wèn)題）呢？已證明，雖然我們可能不知道一個(gè)能給我們精確答案的好算法，但我們可能知道能給出近似結(jié)果的好算法。

大O符號(hào)給出了一個(gè)算法的性能的上界（upper bound）。與之相反的是下界（lower bound），也就是說(shuō)，我們知道其復(fù)雜度在一些初始值之后就永遠(yuǎn)不會(huì)好于某個(gè)函數(shù)。下界的符號(hào)表示是Ω(n)，稱為big-Omega，精確的定義是，如果存在正常數(shù)c和n0，使得f(n)≥ cg(n)≥0對(duì)所有n≥n0成立，則我們稱Ω(f(n))=g(n)。定義了大O和big-Omega之后，我們還可以定義同時(shí)有上界和下界的情況。這就是big-Theta，我們說(shuō)Θ(f(n))=g(n)當(dāng)且僅當(dāng)O(f(n))=g(n)且Ω(f(n))=g(n)。于是我們知道算法運(yùn)行時(shí)間的下界和上界是同一個(gè)函數(shù)，且用相同的常數(shù)縮放。你可以想象為算法的運(yùn)行時(shí)間位于圍繞該函數(shù)的一個(gè)帶狀區(qū)域中。

1.3使用棧求解股票跨度

現(xiàn)在我們回到股票跨度問(wèn)題。我們已經(jīng)找到了一個(gè)復(fù)雜度為O(n(n-1/2))的算法。根據(jù)我們之前的討論，這等價(jià)于O(n2)。能做得更好嗎？回到圖1-1，注意到，當(dāng)處于第6天時(shí)，我們不必與之前每一天進(jìn)行比較直至第1天。因?yàn)槲覀円呀?jīng)遍歷了每一天才來(lái)到第6天，所以已經(jīng)“知道”第2，3，4，5天的報(bào)價(jià)小于或等于第6天。如果我們用某種方法保存這些信息，就不必進(jìn)行所有這些比較，只需與第1天的報(bào)價(jià)進(jìn)行比較即可。

這是一種通用的模式。設(shè)想你位于第k天。如果第k-1天的股票報(bào)價(jià)小于或等于第k天的股票報(bào)價(jià)，于是我們有quotes[k-1]≤quotes[k]或等價(jià)的quotes[k]≥quotes[k-1]，則算法接下來(lái)甚至沒(méi)有再與第k-1天進(jìn)行比較的必要了。為什么？考慮未來(lái)的第k+j天，如果其報(bào)價(jià)小于第k天的報(bào)價(jià)，即quotes[k+j]＜quotes[k]，則我們不必再將它與第k-1天進(jìn)行比較，因?yàn)閺膋+j開(kāi)始的跨度結(jié)束于k。如果第k+j天的報(bào)價(jià)大于第k天的報(bào)價(jià)，則我們已經(jīng)知道必然有quotes[k+j]≥quotes[k-1]，因?yàn)閝uotes[k+j]≥quotes[k]且quotes[k]≥quotes[k-1]。因此每次當(dāng)我們?yōu)橛?jì)算某天的跨度而向后搜索跨度的末端時(shí)，就可丟棄所有報(bào)價(jià)小于或等于這天的那些天，而且在計(jì)算任何未來(lái)的跨度時(shí)都可排除丟棄的這些天。一般而言，在每一天，你只需與直接在你視線中的那些天進(jìn)行比較。

下面的比喻可能會(huì)有助于理解：請(qǐng)看圖1-4，設(shè)想你位于第6天對(duì)應(yīng)的柱子的頂端，你向后平視，不要向下看，則只會(huì)看到第1天對(duì)應(yīng)的柱子，而這也是需要與第6天比較股票價(jià)格的唯一一天。

這意味著在算法1-1第5行開(kāi)始的內(nèi)層循環(huán)，我們開(kāi)始與之前的每一天進(jìn)行比較是浪費(fèi)時(shí)間的。我們可以使用某種機(jī)制，隨手可得已建立最大跨度的范圍，從而避免這種浪費(fèi)。

為了實(shí)現(xiàn)這種機(jī)制，我們可以使用一種稱為棧（stack）的特殊數(shù)據(jù)結(jié)構(gòu)。棧是一種簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，我們可以逐個(gè)向其中放入數(shù)據(jù)，也可以提取這些數(shù)據(jù)。每次我們?nèi)〕龅臄?shù)據(jù)都是之前最后放入的。棧的工作機(jī)制像是餐館里的一疊托盤(pán)，每個(gè)托盤(pán)都堆疊在其他托盤(pán)上面。我們只能取頂端的托盤(pán)，也只能新加托盤(pán)到頂端。由于最后加入的托盤(pán)最先被移出，因此我們稱棧是一種后進(jìn)先出（Last In First Out，LIFO）的數(shù)據(jù)結(jié)構(gòu)。在圖1-5中，可以看到在類似托盤(pán)操作的棧中添加和刪除項(xiàng)的操作。

當(dāng)我們討論數(shù)據(jù)結(jié)構(gòu)時(shí)，需要描述在數(shù)據(jù)結(jié)構(gòu)上可以執(zhí)行什么操作。對(duì)數(shù)組，我們看到了創(chuàng)建數(shù)組和訪問(wèn)元素兩個(gè)操作。對(duì)棧，基于前面的描述，五種棧操作是：

? CreateStack()：創(chuàng)建一個(gè)空棧。

? Push(S，i)：將項(xiàng)i壓入棧S的棧頂。

? Pop(S)：將棧S棧頂?shù)捻?xiàng)彈出，返回此項(xiàng)。如果?？?，此操作不被允許，我們得到一個(gè)錯(cuò)誤。

? Top(S)：得到棧S棧頂項(xiàng)的值，但并不將其移出，棧保持不變。如果棧空，此操作不被允許，我們得到一個(gè)錯(cuò)誤。

? Is Stack Empty(S)：若棧S空，返回TRUE，否則返回FALSE。

在實(shí)際中棧是有限的：在達(dá)到限制之前我們只能向其中壓入一定數(shù)量的元素——畢竟一臺(tái)計(jì)算機(jī)的內(nèi)存有限。在棧的實(shí)際實(shí)現(xiàn)中，還有額外的操作來(lái)檢查棧中元素的數(shù)目（其大?。┮约皸Ｊ欠駶M。這些操作與我們用偽代碼描述的算法無(wú)關(guān)，因此不再對(duì)它們進(jìn)行討論。對(duì)我們將要討論的其他數(shù)據(jù)結(jié)構(gòu)中的相關(guān)操作也是如此。

如算法1-2所示，可以使用棧來(lái)實(shí)現(xiàn)前面提出的求解股票跨度問(wèn)題的思路。與之前的算法一樣，在算法開(kāi)始的第1行我們創(chuàng)建了一個(gè)大小為n的空數(shù)組。由跨度定義，第1天的跨度為1，于是我們?cè)诘?行據(jù)此對(duì)spans[0]進(jìn)行初始化。這一次我們使用一個(gè)棧來(lái)保存要比較的那些天。為此，我們?cè)诘?行創(chuàng)建了一個(gè)空棧。在算法開(kāi)始我們有一個(gè)不起眼的事實(shí)：第1天的股票價(jià)格不會(huì)比它自身更低，因此在第4行我們將0即第1天的索引壓入棧中。

第5～12行的循環(huán)處理隨后的每一天。第6～7行的內(nèi)層循環(huán)查看向后時(shí)間，尋找股票價(jià)格高于當(dāng)前處理這天的最近一天。具體方法是，只要棧頂這天的股票價(jià)格小于或等于當(dāng)前處理這天的價(jià)格（第6行），就從棧中彈出一項(xiàng)（第7行）。如果我們是在計(jì)算第i天跨度時(shí)由于耗盡棧中元素而退出內(nèi)層循環(huán)（第8行），則之前每一天的股票價(jià)格都更低，因此跨度為i+1。我們?cè)诘?行將此值賦予spans[i]。否則（第10行），跨度即為第i天到棧頂那天，于是我們?cè)诘?1行將兩者的差值賦予spans[i]。在返回循環(huán)起點(diǎn)之前，我們將第i天壓入棧頂。這樣，在外層循環(huán)結(jié)束時(shí)，棧中保存的那些天的股票價(jià)格都不小于我們正在處理的這天的股票價(jià)格。這令我們?cè)谘h(huán)的下一步可以只與要緊的那些天進(jìn)行比較，即高于我們視線的那些天，它們才是我們需要的。

算法第6行有一個(gè)值得我們注意的細(xì)節(jié)。如果S為空，則對(duì)Top(S)求值是一個(gè)錯(cuò)誤。但由于條件表達(dá)式求值的一個(gè)重要性質(zhì)——短路求值（short circuit evaluation），錯(cuò)誤并不會(huì)發(fā)生。這條性質(zhì)意味著：當(dāng)我們對(duì)一個(gè)包含邏輯布爾運(yùn)算符的表達(dá)式進(jìn)行求值時(shí)，只要知道最終結(jié)果就立即停止對(duì)表達(dá)式的求值，而不必再對(duì)表達(dá)式的任何剩余部分求值。以表達(dá)式if x＞0 and y＞0為例，如果我們知道x≤0，則不管y的值如何，整個(gè)表達(dá)式都為假，完全沒(méi)必要對(duì)表達(dá)式的第二部分進(jìn)行求值。類似地，在表達(dá)式if x＞0 or y＞0中，如果我們知道x＞0，則沒(méi)有必要對(duì)表達(dá)式的第二部分即包含y的部分進(jìn)行求值，因?yàn)槲覀円呀?jīng)知道當(dāng)?shù)谝徊糠譃檎鏁r(shí)整個(gè)表達(dá)式即為真。表1-2顯示了用and或or運(yùn)算符的兩部分布爾表達(dá)式的一般情況。陰影行表示表達(dá)式的結(jié)果不依賴于第二部分，因此一旦我們知道了第一部分的值就可以停止對(duì)表達(dá)式的求值。采用短路求值機(jī)制，當(dāng)算法1-2中的IsStackEmpty(S)返回TRUE，也就是not IsStackEmpty(S)為假時(shí)，我們將不再試圖對(duì)包含Top(S)的and右側(cè)部分進(jìn)行求值，因而避免了錯(cuò)誤發(fā)生。

在圖1-6中，你可以看到算法是如何工作的以及視線的比喻。在每個(gè)子圖的右側(cè)我們顯示了每個(gè)循環(huán)步開(kāi)始時(shí)棧的內(nèi)容。我們還用填充柱指出了棧中有哪些天，而還未處理的天用虛線柱表示。我們正在計(jì)算跨度的當(dāng)前這天用子圖下方的黑色圈碼表示。

在第一個(gè)子圖中有i=1，我們必須將當(dāng)前這天的股票價(jià)格與棧中那些天的股票價(jià)格進(jìn)行比較，此時(shí)棧中只有第0天。第1天的價(jià)格比第0天高，這意味著從現(xiàn)在開(kāi)始就不再需要與第1天之前的那些天進(jìn)行比較了，我們的視線將止于此。因此在下一步循環(huán)中，i=2，棧中包含數(shù)1。第2天的價(jià)格比第1天低，這意味著如果第3天的價(jià)格低于第2天的價(jià)格，則始于第3天的任何跨度計(jì)算會(huì)終止于第2天，否則，如果第3天的價(jià)格不小于第2天的價(jià)格，就可能終止于第1天。但不會(huì)終止于第0天，因?yàn)榈?天的價(jià)格小于第1天的價(jià)格。i=3和i=4也是類似情況。但當(dāng)?shù)竭_(dá)i=5時(shí)，我們意識(shí)到未來(lái)不再需要與第2，3，4天進(jìn)行比較了。這些天位于第5天的陰影中?；蛘哂靡暰€的比喻說(shuō)，我們的視野暢通無(wú)阻地一直回到第1天。兩者之間的所有東西都可從棧中彈出，棧中將包含5和1，這樣在i=6處，我們最多只需與這兩天進(jìn)行比較。如果某天的價(jià)格大于或等于第5天的價(jià)格，它當(dāng)然也會(huì)大于第4，3，2天的價(jià)格，我們不能確定的只有它是否大于第1天的價(jià)格。當(dāng)我們處理第6天時(shí)，棧中將包含數(shù)6和1。

算法1-2優(yōu)于之前的算法嗎？第5行開(kāi)始的循環(huán)執(zhí)行了n-1次。對(duì)于其中每一次（比如說(shuō)第i次）循環(huán)，第6行開(kāi)始的內(nèi)層循環(huán)中的Pop操作執(zhí)行pi次。這意味著Pop操作將總共執(zhí)行p1+p2+…+pn-1次，外層循環(huán)每一步中執(zhí)行pi次。我們不知道數(shù)pi是什么。但如果你密切關(guān)注算法，會(huì)看到每一天只會(huì)被壓入棧中一次，第0天是在第4行，隨后那些天是在第11行。于是，每一天在第7行從棧中彈出最多只有一次。因此，在算法的整個(gè)執(zhí)行過(guò)程中，在外層循環(huán)的所有步驟中，第6行執(zhí)行不會(huì)超過(guò)n次。換句話說(shuō)，p1+p2+…+pn-1=n，這意味著整個(gè)算法是O(n)的。第7行是算法中執(zhí)行次數(shù)最多的操作，因?yàn)樗趦?nèi)層循環(huán)中，而第5～12行的其余代碼則不是。

繼續(xù)分析可以看到，與只能得到最壞情況估計(jì)的算法1-1進(jìn)行對(duì)比，我們對(duì)算法1-2的估計(jì)也是其性能的下界——算法不可能用少于n步完成這一任務(wù)，因?yàn)槲覀冃枰闅vn天。因此算法1-2的計(jì)算復(fù)雜度也是Ω(n)，于是它也是Θ(n)。

與我們將要遇到的所有其他數(shù)據(jù)結(jié)構(gòu)一樣，棧有很多用途。在計(jì)算機(jī)中LIFO行為是很常見(jiàn)的，因此從機(jī)器語(yǔ)言寫(xiě)成的底層程序到運(yùn)行于超級(jí)計(jì)算機(jī)中的大型程序，你都能在其中發(fā)現(xiàn)棧。這就是數(shù)據(jù)結(jié)構(gòu)存在的首要原因。數(shù)據(jù)結(jié)構(gòu)不是別的什么，而是人類用計(jì)算機(jī)求解問(wèn)題長(zhǎng)年經(jīng)驗(yàn)的精髓。事實(shí)一次又一次地證明，算法在用相似的方式來(lái)組織所處理的數(shù)據(jù)。人們將這些方法整理出來(lái)，使得當(dāng)我們圍繞一個(gè)問(wèn)題尋找方法時(shí)，可直接找到它們，利用它們的功能來(lái)設(shè)計(jì)算法。

本文摘編自機(jī)械工業(yè)出版社華章公司出版的《真實(shí)世界的算法：初學(xué)者指南》

?【文末有福利】股票跨度——真實(shí)世界的算法