算法(algorithm)就是一個(gè)過(guò)程，是一種特殊的過(guò)程。它必須描述為一個(gè)有限步驟序列，且必須在有限時(shí)間內(nèi)結(jié)束。每個(gè)步驟必須是良好定義的，達(dá)到人類(lèi)可用一支筆和一張紙執(zhí)行它的程度。

算法基于我們提供給它的輸入做一些事情，并生成反映其所做工作的一些輸出。算法1-1實(shí)現(xiàn)了我們前面描述的過(guò)程。

• 算法1-1 一個(gè)簡(jiǎn)單的股票跨度算法

SimpleStockSpan(quotes)→spans

• 輸入: quotes,保存n個(gè)股票報(bào)價(jià)的數(shù)組
• 輸出: spans,保存n個(gè)股票跨度的數(shù)組

spans←CreateArray(n) 
for i←0 to n do 
    k←1 
    span_end ← FALSE 
    while i-k ≥ 0 and not span_end do 
       if quotes[i-k] ≤ quotes[i] then 
           k←k+1 
       else 
           span_end ← TRUE 
    spans[i] ← k 
return spans 

算法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í)行，而是易于被人類(lèi)理解。

順便提一下，程序也應(yīng)能被人類(lèi)理解，但并非所有程序都是如此——有很多正在運(yùn)行的計(jì)算機(jī)程序?qū)懙煤茉愀猓y以理解。

每個(gè)算法都有一個(gè)名字，接受一些輸入，并生成一些輸出。在本書(shū)中，算法的名字將采用駱駝拼寫(xiě)法(CamelCase)，輸入會(huì)寫(xiě)在括號(hào)中，輸出用一個(gè)→指示。接下來(lái)的幾行將會(huì)對(duì)算法的輸入和輸出進(jìn)行描述。可以用算法的名字緊接放在括號(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ì)象序列之于人類(lèi)。數(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ù)組可以保存任何類(lèi)型的項(xiàng)，在我們的偽代碼中每個(gè)數(shù)組只能保存單一類(lèi)型的項(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è)保存相同類(lèi)型項(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)算法已完全清晰后再回到這里。

關(guān)于作者：帕諾斯·盧里達(dá)斯(Panos Louridas)，曼徹斯特大學(xué)軟件工程博士，現(xiàn)為雅典經(jīng)濟(jì)與商業(yè)大學(xué)管理科學(xué)與技術(shù)系副教授。在加入高校之前，曾在投資銀行擔(dān)任高級(jí)軟件工程師。

本文摘編自《真實(shí)世界的算法：初學(xué)者指南》，經(jīng)出版方授權(quán)發(fā)布。