初學(xué)者指南：什么是算法？11行偽代碼給你講明白
本文轉(zhuǎn)載自微信公眾號「大數(shù)據(jù)DT（ID：hzdashuju）」，作者帕諾斯·盧里達(dá)斯（Panos Louridas） 。轉(zhuǎn)載本文請聯(lián)系大數(shù)據(jù)DT（ID：hzdashuju）公眾號。
算法(algorithm)就是一個(gè)過程，是一種特殊的過程。它必須描述為一個(gè)有限步驟序列，且必須在有限時(shí)間內(nèi)結(jié)束。每個(gè)步驟必須是良好定義的，達(dá)到人類可用一支筆和一張紙執(zhí)行它的程度。
算法基于我們提供給它的輸入做一些事情，并生成反映其所做工作的一些輸出。算法1-1實(shí)現(xiàn)了我們前面描述的過程。
- 算法1-1 一個(gè)簡單的股票跨度算法
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àn)槟菢訒仁刮覀兲幚砼c算法邏輯無關(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è)名字，接受一些輸入，并生成一些輸出。在本書中，算法的名字將采用駱駝拼寫法(CamelCase)，輸入會寫在括號中，輸出用一個(gè)→指示。接下來的幾行將會對算法的輸入和輸出進(jìn)行描述?？梢杂盟惴ǖ拿志o接放在括號中的輸入來調(diào)用(call)算法。
一旦算法編寫好，就可以將其作為一個(gè)黑盒來處理，可以給它一些輸入，黑盒則會返回算法的輸出。當(dāng)用一種程序設(shè)計(jì)語言實(shí)現(xiàn)一個(gè)算法時(shí)，它就是一個(gè)具名的計(jì)算機(jī)代碼片段——函數(shù)(function)。在一個(gè)計(jì)算機(jī)程序中，我們調(diào)用實(shí)現(xiàn)算法的函數(shù)。
某些算法不生成輸出，當(dāng)然也就不會顯式返回結(jié)果。取而代之的是，它們的行為影響上下文的某部分。例如，我們可能提供給算法一個(gè)空間，供其寫入結(jié)果。在此情況下，在傳統(tǒng)意義上算法并非返回輸出結(jié)果，但無論如何算法是有輸出的，即它影響上下文發(fā)生的變化。
某些程序設(shè)計(jì)語言會區(qū)分顯式返回結(jié)果的具名程序代碼片段——稱為函數(shù)(function)，以及不返回結(jié)果但可能有其他副作用的具名程序代碼片段——稱為過程(procedure)。這種差異來源于數(shù)學(xué)，數(shù)學(xué)上的函數(shù)是必須返回值的。對我們來說，當(dāng)一個(gè)算法編碼為實(shí)際程序時(shí)，既可以是一個(gè)函數(shù)也可以是一個(gè)過程。
我們的偽代碼中使用一些用粗體表示的關(guān)鍵字，如果你對計(jì)算機(jī)和程序設(shè)計(jì)語言的工作方式有所了解，這些關(guān)鍵字的含義就是不言自明的了。
我們使用字符←表示賦值，用等號(=)表示相等比較。我們采用常用的五個(gè)符號(+，-，/，×，·)表示四種數(shù)學(xué)運(yùn)算，后兩個(gè)符號都表示乘法，這兩個(gè)符號我們都會使用，基于美學(xué)考慮進(jìn)行選擇。我們將不會使用任何關(guān)鍵字或符號對偽代碼分塊，分塊是通過縮進(jìn)來表示的。
在這個(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ī)，就像對象序列之于人類。數(shù)組是元素的有序序列，這些元素存儲在計(jì)算機(jī)內(nèi)存中。為了獲得保存元素所需的空間并創(chuàng)建一個(gè)保存n個(gè)元素的數(shù)組，可調(diào)用算法1-1第1行中的CreateArray算法。
如果你熟悉數(shù)組，可能就會奇怪創(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í)其中沒有元素，只有保存元素所需的空間。算法負(fù)責(zé)調(diào)用CreateArray(n)來將實(shí)際數(shù)據(jù)填充到數(shù)組中。
對數(shù)組A，我們用A[i]表示其第i個(gè)元素，訪問該元素也是用該符號。一個(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ī)語言中的數(shù)組都是如此，你最好現(xiàn)在就熟悉這種機(jī)制。這非常常見，當(dāng)遍歷一個(gè)大小為n的數(shù)組時(shí)，我們是從位置0遍歷到位置n-1。
在我們的算法中，當(dāng)我們說某個(gè)對象的取值是從數(shù)x到數(shù)y(假定x小于y)時(shí)，意思是從x到y(tǒng)(但不包含)的所有值，參見算法第2行。
我們假定無論i的值是什么，訪問第i個(gè)元素都花費(fèi)相同的時(shí)間。因此訪問A[0]與訪問A[n-1]需要相同的時(shí)間。這是數(shù)組的一個(gè)非常重要的特性：對元素的訪問是一致的，都花費(fèi)常量時(shí)間。當(dāng)我們通過索引訪問數(shù)組元素時(shí)，數(shù)組不需要搜索此元素。
關(guān)于算法描述中的符號表示，我們用小寫字母表示算法中的變量。但當(dāng)變量表示一個(gè)數(shù)據(jù)結(jié)構(gòu)時(shí)，我們會使用大寫字母來令其突出，如數(shù)組A。但這并非必要。當(dāng)我們希望給變量起一個(gè)包含很多單詞的名字時(shí)，我們會使用下劃線(_)，如a_connector。這是必要的，因?yàn)橛?jì)算機(jī)不理解由一組空格分隔的單詞構(gòu)成單個(gè)變量名的方式。
算法1-1使用數(shù)組保存數(shù)值。數(shù)組可以保存任何類型的項(xiàng)，在我們的偽代碼中每個(gè)數(shù)組只能保存單一類型的項(xiàng)。大多數(shù)程序設(shè)計(jì)語言中也都是如此。
例如，可以創(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)”會是什么，由編程所使用的語言所決定。所有程序設(shè)計(jì)語言都提供表示有意義的東西的方法。
一種特別有用的數(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ù)留，可用來保存元素。
- 正如我們已經(jīng)看到的，對一個(gè)數(shù)組A，A[i]訪問其第i個(gè)元素，而且訪問數(shù)組中任何元素都花費(fèi)相同時(shí)間。若i<0，則試圖訪問A[i]會產(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í)，就會推進(jìn)循環(huán)到第1，2，…，n-1天。
我們使用變量(variable)k指示當(dāng)前跨度的長度——在我們的偽代碼中，變量就是一個(gè)引用某些數(shù)據(jù)的名字，那些數(shù)據(jù)的內(nèi)容，或者更精確地說，變量的值(value)，在算法執(zhí)行的過程中是可以改變的，變量這個(gè)術(shù)語因而得名。當(dāng)我們開始計(jì)算一個(gè)跨度時(shí)，k的值總是1，我們是在第3行設(shè)置這個(gè)初值的。
我們還使用了一個(gè)指示變量(indicator variable)span_end。指示變量取值TRUE或FALSE，指出某事成立或不成立。當(dāng)我們到達(dá)一個(gè)跨度的末端時(shí)，變量span_end的值將為真。
在開始計(jì)算每個(gè)跨度時(shí)，span_end為假，如第4行所示。第5～9行的內(nèi)層循環(huán)計(jì)算跨度的長度。第5行告訴我們，只要跨度還未結(jié)束，就回退盡可能長的時(shí)間。我們能回退多遠(yuǎn)由條件i-k≥0決定：回退到索引i-k指示的這一天檢查跨度是否結(jié)束，而索引不能為0，因?yàn)?對應(yīng)第1天。
第6行檢查跨度是否結(jié)束。如果跨度未結(jié)束，則在第7行增加其長度。否則，我們注意到，第9行設(shè)置跨度結(jié)束，從而循環(huán)會在回到第5行后終止。
第2～10行的外層循環(huán)在第10行結(jié)束一次循環(huán)時(shí)，我們在此將k的值保存到數(shù)組spans的正確位置。在退出循環(huán)后的第11行，我們返回spans，它保存著算法的結(jié)果。
注意，初始時(shí)我們設(shè)定i=0和k=1。這意味著在最早的時(shí)刻第5行的條件必定為假。這是理所應(yīng)當(dāng)?shù)模驗(yàn)榈?天的跨度只能為1。
此時(shí)此刻，記住我們曾說過的關(guān)于算法、筆和紙的內(nèi)容。理解一個(gè)算法的最好方法就是去手動執(zhí)行它。
在任何時(shí)候如果一個(gè)算法看起來有些復(fù)雜，或者你不確定是否已完全理解它，就用紙和筆寫下執(zhí)行它求解某個(gè)例子的過程。這種方法會節(jié)省你很多時(shí)間，雖然它看起來有點(diǎn)老套。如果對算法1-1還有不明確的地方，馬上嘗試這種方法，當(dāng)算法已完全清晰后再回到這里。
關(guān)于作者：帕諾斯·盧里達(dá)斯(Panos Louridas)，曼徹斯特大學(xué)軟件工程博士，現(xiàn)為雅典經(jīng)濟(jì)與商業(yè)大學(xué)管理科學(xué)與技術(shù)系副教授。在加入高校之前，曾在投資銀行擔(dān)任高級軟件工程師。
本文摘編自《真實(shí)世界的算法：初學(xué)者指南》，經(jīng)出版方授權(quán)發(fā)布。
