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

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

• 算法1-1 一個簡單的股票跨度算法

SimpleStockSpan(quotes)→spans

• 輸入: quotes,保存n個股票報價的數(shù)組
• 輸出: spans,保存n個股票跨度的數(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展示了如何描述算法。我們并不使用某種計算機語言，因為那樣會迫使我們處理與算法邏輯無關(guān)的實現(xiàn)細(xì)節(jié)，我們使用的是某種偽代碼(pseudocode)形式。

偽代碼是一種介于真正的程序代碼和非形式化描述之間的形式。它使用一種結(jié)構(gòu)化格式，并采用一組具有特定含義的詞匯。但是，偽代碼不是真正的計算機代碼。它并不是為了被計算機執(zhí)行，而是易于被人類理解。

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

每個算法都有一個名字，接受一些輸入，并生成一些輸出。在本書中，算法的名字將采用駱駝拼寫法(CamelCase)，輸入會寫在括號中，輸出用一個→指示。接下來的幾行將會對算法的輸入和輸出進(jìn)行描述?？梢杂盟惴ǖ拿志o接放在括號中的輸入來調(diào)用(call)算法。

一旦算法編寫好，就可以將其作為一個黑盒來處理，可以給它一些輸入，黑盒則會返回算法的輸出。當(dāng)用一種程序設(shè)計語言實現(xiàn)一個算法時，它就是一個具名的計算機代碼片段——函數(shù)(function)。在一個計算機程序中，我們調(diào)用實現(xiàn)算法的函數(shù)。

某些算法不生成輸出，當(dāng)然也就不會顯式返回結(jié)果。取而代之的是，它們的行為影響上下文的某部分。例如，我們可能提供給算法一個空間，供其寫入結(jié)果。在此情況下，在傳統(tǒng)意義上算法并非返回輸出結(jié)果，但無論如何算法是有輸出的，即它影響上下文發(fā)生的變化。

某些程序設(shè)計語言會區(qū)分顯式返回結(jié)果的具名程序代碼片段——稱為函數(shù)(function)，以及不返回結(jié)果但可能有其他副作用的具名程序代碼片段——稱為過程(procedure)。這種差異來源于數(shù)學(xué)，數(shù)學(xué)上的函數(shù)是必須返回值的。對我們來說，當(dāng)一個算法編碼為實際程序時，既可以是一個函數(shù)也可以是一個過程。

我們的偽代碼中使用一些用粗體表示的關(guān)鍵字，如果你對計算機和程序設(shè)計語言的工作方式有所了解，這些關(guān)鍵字的含義就是不言自明的了。

我們使用字符←表示賦值，用等號(=)表示相等比較。我們采用常用的五個符號(+，-，/，×，·)表示四種數(shù)學(xué)運算，后兩個符號都表示乘法，這兩個符號我們都會使用，基于美學(xué)考慮進(jìn)行選擇。我們將不會使用任何關(guān)鍵字或符號對偽代碼分塊，分塊是通過縮進(jì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)存并標(biāo)記它為數(shù)組所用。

CreateArray(n)調(diào)用做了所需的一切，它返回一個可容納n個元素的數(shù)組，初始時其中沒有元素，只有保存元素所需的空間。算法負(fù)責(zé)調(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)在就熟悉這種機制。這非常常見，當(dāng)遍歷一個大小為n的數(shù)組時，我們是從位置0遍歷到位置n-1。

在我們的算法中，當(dāng)我們說某個對象的取值是從數(shù)x到數(shù)y(假定x小于y)時，意思是從x到y(tǒng)(但不包含)的所有值，參見算法第2行。

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

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

算法1-1使用數(shù)組保存數(shù)值。數(shù)組可以保存任何類型的項，在我們的偽代碼中每個數(shù)組只能保存單一類型的項。大多數(shù)程序設(shè)計語言中也都是如此。

例如，可以創(chuàng)建十進(jìn)制數(shù)數(shù)組、分?jǐn)?shù)數(shù)組、表示人的項的數(shù)組以及另一個表示地址的項的數(shù)組，但不可以創(chuàng)建一個既包含十進(jìn)制數(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表示我們正在計算跨度的當(dāng)前這一天。初始時，處于第0天這一最早的時間點。每次執(zhí)行第2行代碼時，就會推進(jìn)循環(huán)到第1，2，…，n-1天。

我們使用變量(variable)k指示當(dāng)前跨度的長度——在我們的偽代碼中，變量就是一個引用某些數(shù)據(jù)的名字，那些數(shù)據(jù)的內(nèi)容，或者更精確地說，變量的值(value)，在算法執(zhí)行的過程中是可以改變的，變量這個術(shù)語因而得名。當(dāng)我們開始計算一個跨度時，k的值總是1，我們是在第3行設(shè)置這個初值的。

我們還使用了一個指示變量(indicator variable)span_end。指示變量取值TRUE或FALSE，指出某事成立或不成立。當(dāng)我們到達(dá)一個跨度的末端時，變量span_end的值將為真。

在開始計算每個跨度時，span_end為假，如第4行所示。第5～9行的內(nèi)層循環(huán)計算跨度的長度。第5行告訴我們，只要跨度還未結(jié)束，就回退盡可能長的時間。我們能回退多遠(yuǎn)由條件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)當(dāng)?shù)?，因為?天的跨度只能為1。

此時此刻，記住我們曾說過的關(guān)于算法、筆和紙的內(nèi)容。理解一個算法的最好方法就是去手動執(zhí)行它。

在任何時候如果一個算法看起來有些復(fù)雜，或者你不確定是否已完全理解它，就用紙和筆寫下執(zhí)行它求解某個例子的過程。這種方法會節(jié)省你很多時間，雖然它看起來有點老套。如果對算法1-1還有不明確的地方，馬上嘗試這種方法，當(dāng)算法已完全清晰后再回到這里。

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

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