1.2　算法基礎

許多初學者認為，學習編程就是學習新的編程語言、技術和框架，其實計算機算法更重要。從C語言、C++、Java、C#到Python，雖然編程語言種類繁多，但經典的算法卻是萬變不離其宗。所以，練好算法這門“內功”，再結合新技術這些“招式”，才能真正地成為一名合格的程序員。

1.2.1　算法的定義

算法是一組完成任務的指令，因此有計算機工作者這樣定義：為了解決某個或某類問題，需要把指令表示成一定的操作序列，操作序列包括一組操作，每個操作都完成特定的功能。簡單來說，算法是解決特定問題的步驟描述，即處理問題的策略。

首先來看一個例子—經典問題“百錢買百雞”。用一百錢買一百只雞，雞的品種有公雞、母雞和雛雞，價格分別是：一只公雞5錢，一只母雞3錢，三只雛雞1錢。要求每個品種的雞至少買一只，問怎樣買才能用一百錢買一百只雞。

整理題干信息，可以得出以下兩個限制性條件：

（1）買的公雞、母雞、雛雞的總數量是100只，如圖1.2所示。

（2）花的錢數是100錢，根據不同類型的雞價格不同，可以有如圖1.3所示的式子。

圖1.2　條件1

圖1.3　條件2

算法解析如下：

（1）根據條件2，計算每一種雞最多能買多少只。

① 如果盡可能多地購買公雞，那么公雞的購買范圍是1～19只，不能超過20只。因為，如果購買20只公雞，就需要花費100錢（20*5=100），這樣無法購買母雞和雛雞，不符合題意。

② 如果盡可能多地購買母雞，那么母雞的購買范圍是1～32只，不能為33只，否則需要花99錢（3*33=99），公雞和雛雞就沒有辦法購買了。

③ 3只雛雞需要花1錢，所以要買雛雞，就得一起買3只雛雞，因此雛雞的數量應為3的倍數，故遞增的步長可以設為3。同理，如果盡可能多地購買雛雞，雛雞的購買范圍應為3～99只。

（2）使用某種編程語言，在公雞、母雞、雛雞的可購買數量范圍內列出三重循環，進行窮舉，使兩個代數式均成立，則為百錢買百雞的解。

下面來看一下如何使用Python語言實現百錢買百雞問題的求解。

【實例1.1】　百錢買百雞。（實例位置：資源包\Code\01\01）

具體代碼如下：

運行結果如圖1.4所示?？梢?，有3種購買方法：4公雞+18母雞+78雛雞；8公雞+11母雞+81雛雞；12公雞+4母雞+84雛雞。

實例1.1中的算法解析思路和Python代碼實現，整個過程就是算法的實現過程。

圖1.4　運行結果

1.2.2　算法的特性

算法主要用于解決“做什么”和“怎么做”的問題，因為解決問題的步驟需要在有限時間內完成，而且解決問題可能有不止一種方法，所以在進行算法分析時最為核心的考察要點是算法的速度。另外，操作步驟中不可以有不明確的語句，使得步驟無法繼續進行下去。

總之，一個算法必須滿足有輸入、有輸出、確定性、有限性、有效性五大特性，如圖1.5所示。

圖1.5　算法的五大特性

1．有輸入

一個程序中，算法和數據是相互關聯的。算法中需要輸入數據的值，例如：

age=input("您的年齡是：")                        #輸入變量值

注意，輸入可以是多個，也可以是零個。零個輸入并不代表這個算法沒有輸入，而是這個輸入沒有直觀地顯現出來，隱藏在了算法本身中。

2．有輸出

一個算法，需要輸出一定的結果，沒有輸出的算法是沒有意義的。有的算法輸出的是數值，有的輸出是圖形，有的輸出并不是那么顯而易見。例如：

上述3行代碼的輸出結果如下：

1314
^_^

3．確定性

算法中，每條指令及每個步驟的表述都應該是明確的，使計算機能“聽懂”，并能照著做，不能存在任何的歧義和模糊性。

日常生活中，我們經常會遇到一些含義不明確的語句。當然，人腦可以根據常識、語境等，自動補充信息使其明確，但即便如此，仍然有可能理解錯誤（見圖1.6）。計算機不比人腦，它只會嚴格按照指令一步步地執行，無法處理有歧義或表述不明的情況，更不會根據算法的意義來揣測每個步驟的意思，所以算法的每一步都必須給出確定的信息和指令。

圖1.6　生活中的不確定表述

4．有限性

一個算法，如果在執行有限步驟后能夠實現，或者在有限時間內能夠完成，就稱該算法具有有限性。例如，在“百錢買百雞”代碼的for循環中，(1,20)、(1,33)、(3,99,3)這幾個范圍保證了程序的有限性。如果沒有此條件，for循環就會無終止地進行，程序也就進入了死循環。

有的算法在理論上滿足有限性要求，即可在有限的步驟后完成，但實際上計算機可能會執行一天、一年、十年等。算法的核心就是速度，過慢的算法實際上是沒有什么意義的。當然，有些算法非常復雜，確實需要較長的運算時間。但就普通開發而言，快捷、高效是核心，也是進行算法設計時的關鍵考量要素。

5．有效性

算法的有效性是指每個步驟都必須有效地執行，得到確定的結果，且能方便地用來解決一類問題。如下代碼中的“z=x/y;”就是一個無效語句，因為0不可以做分母。

1.2.3　算法的性能分析與度量

算法是解決問題的方法，但解決問題的方法通常不止一個，方法多了，自然而然地就有了優劣之分。這就好比，一個人掃地時，人們往往只會關注掃地任務是否完成；然而當有兩三個人同時掃地時，人們就有了比較，可以根據某個評定標準判斷誰掃的更好。比如，有人認為A好，因為他掃的快；有人認為B好，因為他掃的干凈，等等。

那么，算法的優劣該怎樣評定呢？可以從算法的性能指標和算法效率等方面來衡量。

1．算法的性能指標

評定一個算法的優劣，主要有以下幾個指標。

（1）正確性。一個算法必須正確，即能解決提出的問題，才有實際的價值。正確性是考量算法時最重要的指標，編程人員應用合適的算法語言實現正確的功能。

（2）友好性。算法實現的功能最終是要給用戶使用的，自然要考慮用戶的使用習慣，使其具有良好的使用性，人們愿意用，且用著方便。

（3）可讀性。一個算法，在其誕生和使用過程中可能會進行多人、多次的修改，也可能會被移植到其他功能中去，因此算法應當是可讀的（代碼易于理解），以方便程序員對其分析、修改和移植。

（4）健壯性。算法的實際應用中，有時會出現不合理的數據輸入或非法操作，因此算法必須具有一定的健壯性，能夠對這些問題進行檢查和糾正。讀者在剛開始學習算法時，可以忽略健壯性的存在，但在后續的開發中，一定要努力讓自己的算法具有一定的健壯性。

（5）效率。算法的效率主要指執行算法時對計算機資源的消耗程度，包括對計算機內存的消耗和對計算機運行時間的消耗，兩者統稱為時空效率。一個算法只有正確性而無效率，是沒有意義的，因此也經常把效率用作評定算法是否正確的指標。如果一個算法需要執行幾年，甚至幾百年，那么無疑這個算法會被評為是錯誤的。

2．算法效率的度量

度量算法效率的方法有兩種：事后計算和事前分析估算。

（1）事后計算。先實現算法，然后運行程序，測算其對時間和空間的消耗。這種度量方法有很多弊端，由于算法的運行與計算機的軟硬件等環境因素有關，不容易發現算法本身的優劣。同樣的算法，用不同的編譯器編譯出的目標代碼不一樣多，完成算法所需的時間也不相同。當計算機的存儲空間較小時，算法運行時間會延長。

（2）事前分析估算。這種度量方法通過比較算法的復雜性，估算算法的效率高低。算法的復雜性與計算機的軟硬件環境無關，僅與計算耗時和存儲需求有關。算法復雜性的度量可以分為空間復雜度度量和時間復雜度度量。

3．算法的時間復雜度

算法的時間復雜度主要用于衡量算法執行時需要消耗的時間規模。

執行算法所用的時間包括程序編譯時間和運行時間，由于算法編譯成功后可以多次運行，因此通常忽略掉編譯時間，只討論運行時間。

算法的運行時間取決于加、減、乘、除等基本運算的時長，參加運算的數據量，以及計算機硬件和操作環境等因素。其中，最為關鍵的因素是問題規模，也就是運算數據量的多少。同等條件下，問題規模越大，運行時間越長。例如，求1+2+3+…+n的算法，計算量的大小取決于問題規模n為多大，n的規模決定了基本運算的執行次數，即運算規模。因此，算法運行時間一定是問題規模n的某個函數，記作T(n)。當n不斷變化時，T(n)也會不斷變化。為了弄清楚T(n)的變化規律，引入“時間復雜度”這一概念。

一般情況下，若有某個輔助函數f(n)，使得當n趨近于無窮大時，T(n) / f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數，記作T(n)=O(f(n))。O(f(n))表示的是算法的漸進時間復雜度，這種表示法被稱為大O表示法。需要注意，時間復雜度得出的不是時間量，而是一種增長趨勢。

例如，當一個算法的時間復雜度為常量，不隨數據量n的大小改變時，可表示為O(1)；當一個算法的時間復雜度與n成線性比例關系時，可表示為O(n)。

4．算法的空間復雜度

算法的空間復雜度是指算法執行過程中需要的輔助空間數量。這里，輔助空間數量不是程序指令、常數、指針等占用的存儲空間，也不是輸入／輸出數據占用的存儲空間，而是除此以外算法臨時開辟的存儲空間。

算法的空間復雜度分析方法同時間復雜度相似。設S(n)表示算法的空間復雜度，則S(n)=O(f(n))。

1.2.4　大O表示法

下面通過一個實例，介紹如何使用大O表示法判斷一段程序的時間復雜度（請讀者從數學函數的角度思考以下講解內容）。

【實例1.2】　計算a、b、c的值。（實例位置：資源包\Code\01\02）

已知a+b+c=1000且a2+b2=c2（a, b, c都是自然數，且范圍均為0～1000），求a, b, c的所有可能組合。代碼如下：

本例程序大約需要4分鐘，才能運行出結果，如圖1.7所示。

圖1.7　運行結果

將上述代碼做如下修改：

比較這兩段代碼，發現代碼的第3行有所不同，從一個for循環變成了一個減法基本運算。第二段代碼的最終運行時間不到1分鐘，結果依然是圖1.7的內容。從速度上看，第二段代碼更快。也就是說，第二段代碼的算法要比第一段代碼成熟，執行效率更高。這是為什么呢？一起來分析一下。

（1）首先來算下第一段代碼的時間復雜度。

設時間為f (n)，這段代碼用到了3層for循環，每層循環遍歷一次0～1000，時間復雜度都是1000，3層嵌套for循環的時間復雜度是各層for循環時間復雜度的乘積，即f (n)=1000*1000*1000，而for循環之后的if和print兩條語句是基本語句，暫且算成是2。因此，第一段程序的時間復雜度是：f (n)=1000*1000*1000*2。

如果將for循環的遍歷范圍改成0～n，n是一個變量，那么時間復雜度就變成了一個函數：

f (n)=n*n*n*2=2n3

函數的象限圖如圖1.8所示。將系數從2變為1，f (n)=n3的函數圖雖然沒那么陡峭，但整體趨勢是一樣的。可以這么理解，增加系數形成的象限圖都是f (n)=n3的漸近線，對應的函數是漸近函數。

將一系列表示時間復雜度的漸近函數用T(n)來表示，就變成了如下形式（k為系數）：

T(f (n))= k * f (n)

由于系數k并不影響函數走勢，所以可以忽略k的值，最終T(n)=O(f (n))。

這種形式就是大O表示法，f (n)是T(n)的大O表示法。其中，O(f (n))就是這段代碼的漸近函數的時間復雜度，簡稱時間復雜度，也就是T(n)。

通過上面的分析，可以總結出這樣一條結論：在計算一個算法的時間復雜度時，可以忽略所有的低次冪和最高次冪的系數。這樣做的目的是為了簡化算法分析，使注意力集中在增長率上。

（2）下面來分析一下第二段代碼的時間復雜度。

第二段代碼有兩層for循環，忽略系數，它的時間復雜度就是T(n)=n2，最終的大O表示法為T(n)=O(n2)，復雜度的走勢如圖1.9所示。

圖1.8　立方象限圖

圖1.9　平方象限圖

例如，有這樣一段代碼：

求這段代碼的時間復雜度T(n)，分析如下：

（1）第一個框內的代碼，只有3條基本語句，所以時間復雜度是T₁(n)=3。

（2）第二個框內的代碼，有兩層for嵌套循環和3條基本語句，所以時間復雜度是T₂(n)=n*n*3=n2*3。

（3）第三個框內的代碼，有一層for循環和兩條基本語句，所以時間復雜度是T₃(n)=n*2。

（4）第四個框內的代碼，只有一條基本語句，所以時間復雜度是T₄(n)=1。

（5）整段程序的時間復雜度是T(n)= T₁(n)+ T₂(n)+ T₃(n)+ T₄(n)=3+n2*3+n*2+1= 3n2+2n+4。忽略掉所有的低次冪、最高次冪的系數以及常數，最終的大O表示法是T(n)=O(n2)，其象限圖正是圖1.9。

下面給出算法中常見的大O表示法，如表1.1所示。

表1.1　常見的大O表示法