數(shù)學算法俱樂部

日期：2020年08月15日

正文共：12997字10圖

預(yù)計閱讀時間：33分鐘

來源：《真實世界的算法：初學者指南》

設(shè)想你可以獲得一只股票的每日報價。也就是說，你得到一個數(shù)值序列，每個數(shù)表示一只給定股票在某天的收盤價。這些收盤價已按時間順序排列好。股票市場關(guān)閉的日子沒有對應(yīng)的報價。

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

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

對于很多用計算機來求解的問題，通常都存在多種求解方法，其中一些方法比另外一些更好。這里，“更好”這個詞自身并沒有什么實際意義。當我們說更好時，實際是說某些方面更好。可能是速度方面、內(nèi)存方面或是影響時間和空間等資源的其他方面。我們會對此進行更多的討論，但重要的是從一開始就要記住這一點，因為問題的一個解可能很簡單但按照我們設(shè)置的一些約束或標準并不是最優(yōu)的。

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

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

現(xiàn)在還有一個問題，上面對求解過程的描述并不是一種非常好的方式。在這個世界上，散文是交流幾乎所有事情的極好方式，但提供給計算機的過程除外，因為在描述提供給計算機的東西時，必須十分精確。

如果我們的描述足夠精確，計算機能夠理解我們的過程，就意味著我們已經(jīng)創(chuàng)建了一個程序（program）。但用計算機程序來描述一個過程可能又并非易于人類理解的最佳方式，因為你必須告訴計算機要做的所有細節(jié)，而且是以計算機的工作方式告訴它，而這些不一定與問題的解相關(guān)。一個描述如果足夠詳細、可被計算機理解，對于人類來說可能就過于詳細而難于理解了。

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

1.1算法

?

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

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

每個算法都有一個名字，接受一些輸入，并生成一些輸出。在本書中，算法的名字將采用駱駝拼寫法（CamelCase），輸入會寫在括號中，輸出用一個→指示。接下來的幾行將會對算法的輸入和輸出進行描述。可以用算法的名字緊接放在括號中的輸入來調(diào)用（call）算法。一旦算法編寫好，就可以將其作為一個黑盒來處理，可以給它一些輸入，黑盒則會返回算法的輸出。當用一種程序設(shè)計語言實現(xiàn)一個算法時，它就是一個具名的計算機代碼片段——函數(shù)（function）。在一個計算機程序中，我們調(diào)用實現(xiàn)算法的函數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2運行時間和復(fù)雜度

?

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

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

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

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

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

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

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

1 000這樣的函數(shù)，則可以簡化表示為O(f(n))=n3。為什么可以這樣？因為我們總是可以找到一個值c使得0≤f(n)≤cn3。一般而言，當我們有一個包含多項的函數(shù)時，其最大項會很快主導(dǎo)函數(shù)的增長，因此可以去掉最小的那些項，使用大O符號。因此O(a1nk+a2nk-1 +…+akn+b)=O(nk)。

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

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

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

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

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

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

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

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

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

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

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

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

在圖1-3中，顯示了針對幾個函數(shù)繪制的曲線，而實際上我們在研究算法時n都是自然數(shù)，因此我們預(yù)期看到的是顯示點而非線的散點圖。對數(shù)、線性、對數(shù)線性和多項式函數(shù)當然都是直接對實數(shù)定義的，因此使用正常的函數(shù)定義繪制它們的曲線沒有什么問題。冪運算的解釋通常是針對整數(shù)的，但有理數(shù)指數(shù)的冪也是可能的，因為xa/b=(xa)1/b= ?。于是實數(shù)指數(shù)的冪定義為bx=(elnb)x=exlnb。至于階乘，用一些更高等的數(shù)學知識，已證明可對所有實數(shù)定義（負階乘被當作無窮）。因此我們將復(fù)雜度函數(shù)繪制為曲線是合理的。

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

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

1.3使用棧求解股票跨度

?

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

這是一種通用的模式。設(shè)想你位于第k天。如果第k-1天的股票報價小于或等于第k天的股票報價，于是我們有quotes[k-1]≤quotes[k]或等價的quotes[k]≥quotes[k-1]，則算法接下來甚至沒有再與第k-1天進行比較的必要了。為什么？考慮未來的第k+j天，如果其報價小于第k天的報價，即quotes[k+j]＜quotes[k]，則我們不必再將它與第k-1天進行比較，因為從k+j開始的跨度結(jié)束于k。如果第k+j天的報價大于第k天的報價，則我們已經(jīng)知道必然有quotes[k+j]≥quotes[k-1]，因為quotes[k+j]≥quotes[k]且quotes[k]≥quotes[k-1]。因此每次當我們?yōu)橛嬎隳程斓目缍榷蚝笏阉骺缍鹊哪┒藭r，就可丟棄所有報價小于或等于這天的那些天，而且在計算任何未來的跨度時都可排除丟棄的這些天。一般而言，在每一天，你只需與直接在你視線中的那些天進行比較。

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

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

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

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

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

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

? Pop(S)：將棧S棧頂?shù)捻棌棾?，返回此項。如果?？眨瞬僮鞑槐辉试S，我們得到一個錯誤。

? Top(S)：得到棧S棧頂項的值，但并不將其移出，棧保持不變。如果?？眨瞬僮鞑槐辉试S，我們得到一個錯誤。

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

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

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

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

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

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

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

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

繼續(xù)分析可以看到，與只能得到最壞情況估計的算法1-1進行對比，我們對算法1-2的估計也是其性能的下界——算法不可能用少于n步完成這一任務(wù)，因為我們需要遍歷n天。因此算法1-2的計算復(fù)雜度也是Ω(n)，于是它也是Θ(n)。

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

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

推薦閱讀

《真實世界的算法：初學者指南》

內(nèi)容簡介：

算法的第一本入門書籍，帶領(lǐng)你踏上算法學習之路。本書通過真實世界中需要解決的實際問題來介紹算法，這些算法用偽代碼表示，可以很容易地用計算機語言實現(xiàn)。算法盡量簡單，避免讀者有挫敗感，僅需基本數(shù)學基礎(chǔ)和計算機常識知識。通過真實世界需要解決的實際問題來介紹算法思想。為各領(lǐng)域高效運用算法提供重要指南。

粉絲福利時間

評論區(qū)留言，點贊數(shù)前5可獲得此書?。。?/span>

以48個小時計！

注：若是在活動截止日期后24小時內(nèi)無法取得用戶回復(fù)或聯(lián)系，將按照留言點贊排名順延。

新書上市，長按二維碼了解及購買

—?THE END —

?800萬，這位兩院院士全捐了！

?如果我是數(shù)學老師，有學生問出這個問題，我肯定非常激動！

?把宇宙138億年壓縮到1年：看完懷疑人生

?機器學習中需要了解的 5 種采樣方法

?北大讀博手記：怎樣完成自己的博士生涯？非常具有指導(dǎo)性！

?我眼中的麥克斯韋方程組