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

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

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

SimpleStockSpan(quotes)→spans

• 輸入: quotes,保存n個股票報價的數組
• 輸出: spans,保存n個股票跨度的數組

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展示了如何描述算法。我們并不使用某種計算機語言，因為那樣會迫使我們處理與算法邏輯無關的實現細節，我們使用的是某種偽代碼(pseudocode)形式。

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

順便提一下，程序也應能被人類理解，但并非所有程序都是如此——有很多正在運行的計算機程序寫得很糟糕，難以理解。

每個算法都有一個名字，接受一些輸入，并生成一些輸出。在本書中，算法的名字將采用駱駝拼寫法(CamelCase)，輸入會寫在括號中，輸出用一個→指示。接下來的幾行將會對算法的輸入和輸出進行描述。可以用算法的名字緊接放在括號中的輸入來調用(call)算法。

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

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

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

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

我們使用字符←表示賦值，用等號(=)表示相等比較。我們采用常用的五個符號(+，-，/，×，·)表示四種數學運算，后兩個符號都表示乘法，這兩個符號我們都會使用，基于美學考慮進行選擇。我們將不會使用任何關鍵字或符號對偽代碼分塊，分塊是通過縮進來表示的。

在這個算法中，我們使用了數組(array)。數組是一種保存數據的結構，它允許我們按特定方式操縱其中的數據。我們保存數據并允許在其保存的數據上執行特定操作的結構稱為數據結構(data structure)。因此數組是一種數據結構。

數組之于計算機，就像對象序列之于人類。數組是元素的有序序列，這些元素存儲在計算機內存中。為了獲得保存元素所需的空間并創建一個保存n個元素的數組，可調用算法1-1第1行中的CreateArray算法。

如果你熟悉數組，可能就會奇怪創建數組怎么還需要一個算法。但實際情況的確如此。為了獲得保存數據的一塊內存，你必須至少在計算機中搜索可用內存并標記它為數組所用。

CreateArray(n)調用做了所需的一切，它返回一個可容納n個元素的數組，初始時其中沒有元素，只有保存元素所需的空間。算法負責調用CreateArray(n)來將實際數據填充到數組中。

對數組A，我們用A[i]表示其第i個元素，訪問該元素也是用該符號。一個元素在數組中的位置，如A[i]中的i，被稱為索引(index)。一個n個元素的數組A包含元素A[0]，A[1]，…，A[n-1]。

這可能令你吃驚，因為其首元素是第0個，而尾元素是第n-1個，可能你的預期是第1個和第n個。但是，大多數計算機語言中的數組都是如此，你最好現在就熟悉這種機制。這非常常見，當遍歷一個大小為n的數組時，我們是從位置0遍歷到位置n-1。

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

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

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

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

例如，可以創建十進制數數組、分數數組、表示人的項的數組以及另一個表示地址的項的數組，但不可以創建一個既包含十進制數又包含表示人的項的數組。至于“表示人的項”會是什么，由編程所使用的語言所決定。所有程序設計語言都提供表示有意義的東西的方法。

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

總結一下，數組就是一個保存相同類型項的序列的數據結構。數組支持兩種操作：

• CreateArray(n)創建一個能保存n個元素的數組。數組未初始化，即它不保存任何實際元素，但保存元素所需的空間已預留，可用來保存元素。
• 正如我們已經看到的，對一個數組A，A[i]訪問其第i個元素，而且訪問數組中任何元素都花費相同時間。若i<0，則試圖訪問A[i]會產生錯誤。

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

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

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

在開始計算每個跨度時，span_end為假，如第4行所示。第5～9行的內層循環計算跨度的長度。第5行告訴我們，只要跨度還未結束，就回退盡可能長的時間。我們能回退多遠由條件i-k≥0決定：回退到索引i-k指示的這一天檢查跨度是否結束，而索引不能為0，因為0對應第1天。

第6行檢查跨度是否結束。如果跨度未結束，則在第7行增加其長度。否則，我們注意到，第9行設置跨度結束，從而循環會在回到第5行后終止。

第2～10行的外層循環在第10行結束一次循環時，我們在此將k的值保存到數組spans的正確位置。在退出循環后的第11行，我們返回spans，它保存著算法的結果。

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

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

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

關于作者：帕諾斯·盧里達斯(Panos Louridas)，曼徹斯特大學軟件工程博士，現為雅典經濟與商業大學管理科學與技術系副教授。在加入高校之前，曾在投資銀行擔任高級軟件工程師。

本文摘編自《真實世界的算法：初學者指南》，經出版方授權發布。