數(shù)據(jù)結構與算法是對于程序員來說是很重要的東西，可能很長時間都用不到，可是用到的時候將會大大提高和優(yōu)化代碼的執(zhí)行效率。

引入

先來看一道題，已這道題為例：

如果 a＋b＋c＝1000，且 a＾2＋b＾2＝c＾2（a，b，c 為自然數(shù)），如何求出所有a、b、c可能的組合？

窮舉法、枚舉法

這種方法最麻煩，也是最容易想到的，但是耗時會很長

import timestart＿time ＝ time．time（）for a in range（0， 1001）：

for b in range（0， 1001）：

for c in range（0， 1001）：

＃ 為了防止少寫等號導致代碼運行失誤，將常量放在左邊

if 1000 ＝＝ a ＋ b ＋ c and a＊＊2 ＋ b＊＊2 ＝＝ c＊＊2：

print（＂a， b， c： ｛｝， ｛｝， ｛｝＂．format（a， b， c））

end＿time ＝ time．time（）print（＂用時：｛｝＂．format（end＿time － start＿time））
輸出結果及耗時a， b， c： 0， 500， 500a， b， c： 200， 375， 425a， b， c： 375， 200， 425a， b， c： 500， 0， 500用時：190．22626113891602Process finished with exit code 0優(yōu)化for a in range（0， 1001）：

for b in range（0， 1001）：

c ＝ 1000 － a － b

if a＊＊2 ＋ b＊＊2 ＝＝ c＊＊2：

print（＂a， b， c： ｛｝， ｛｝， ｛｝＂．format（a， b， c））

end＿time ＝ time．time（）print（＂用時：｛｝＂．format（end＿time － start＿time））＃ 耗時a， b， c： 0， 500， 500a， b， c： 200， 375， 425a， b， c： 375， 200， 425a， b， c： 500， 0， 500用時：1．1040208339691162Process finished with exit code 0算法的概念

算法是計算機處理信息的本質，因為計算機程序本質上是一個算法來告訴計算機確切的步驟來執(zhí)行一個指定的任務。一般地，當算法在處理信息時，會從輸入設備或數(shù)據(jù)的存儲地址讀取數(shù)據(jù)，把結果寫入輸出設備或某個存儲地址供以后再調(diào)用。

算法是獨立存在的一種解決問題的方法和思想。

對于算法而言，實現(xiàn)的語言并不重要，重要的是思想。

算法可以有不同的語言描述實現(xiàn)版本（如C描述、C＋＋描述、Python描述等），這里是在用Python語言進行描述實現(xiàn)

算法的五大特性

輸入： 算法具有0個或多個輸入

輸出： 算法至少有1個或多個輸出

有窮性： 算法在有限的步驟之后會自動結束而不會無限循環(huán)，并且每一個步驟可以在可接受的時間內(nèi)完成

確定性：算法中的每一步都有確定的含義，不會出現(xiàn)二義性

可行性：算法的每一步都是可行的，也就是說每一步都能夠執(zhí)行有限的次數(shù)完成

算法效率衡量執(zhí)行時間反應算法效率

對于同一問題，我們給出了兩種解決算法，在兩種算法的實現(xiàn)中，我們對程序執(zhí)行的時間進行了測算，發(fā)現(xiàn)兩段程序執(zhí)行的時間相差懸殊（214．583347秒相比于0．182897秒），由此我們可以得出結論：實現(xiàn)算法程序的執(zhí)行時間可以反應出算法的效率，即算法的優(yōu)劣。

單靠時間值絕對可信嗎？

假設我們將第二次嘗試的算法程序運行在一臺配置古老性能低下的計算機中，情況會如何？很可能運行的時間并不會比在我們的電腦中運行算法一的214．583347秒快多少。

單純依靠運行的時間來比較算法的優(yōu)劣并不一定是客觀準確的！

程序的運行離不開計算機環(huán)境（包括硬件和操作系統(tǒng)），這些客觀原因會影響程序運行的速度并反應在程序的執(zhí)行時間上。那么如何才能客觀的評判一個算法的優(yōu)劣呢？

時間復雜度與“大O記法”

我們假定計算機執(zhí)行算法每一個基本操作的時間是固定的一個時間單位，那么有多少個基本操作就代表會花費多少時間單位。顯然對于不同的機器環(huán)境而言，確切的單位時間是不同的，但是對于算法進行多少個基本操作（即花費多少時間單位）在規(guī)模數(shù)量級上卻是相同的，由此可以忽略機器環(huán)境的影響而客觀的反應算法的時間效率。

對于算法的時間效率，我們可以用“大O記法”來表示。

“大O記法”：對于單調(diào)的整數(shù)函數(shù)f，如果存在一個整數(shù)函數(shù)g和實常數(shù)c＞0，使得對于充分大的n總有f（n）＜＝c＊g（n），就說函數(shù)g是f的一個漸近函數(shù)（忽略常數(shù)），記為f（n）＝O（g（n））。也就是說，在趨向無窮的極限意義下，函數(shù)f的增長速度受到函數(shù)g的約束，亦即函數(shù)f與函數(shù)g的特征相似。

時間復雜度：假設存在函數(shù)g，使得算法A處理規(guī)模為n的問題示例所用時間為T（n）＝O（g（n）），則稱O（g（n））為算法A的漸近時間復雜度，簡稱時間復雜度，記為T（n）

如何理解“大O記法”

對于算法進行特別具體的細致分析雖然很好，但在實踐中的實際價值有限。對于算法的時間性質和空間性質，最重要的是其數(shù)量級和趨勢，這些是分析算法效率的主要部分。而計量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計。例如，可以認為3n2和100n2屬于同一個量級，如果兩個算法處理同樣規(guī)模實例的代價分別為這兩個函數(shù)，就認為它們的效率“差不多”，都為n2級。

最壞時間復雜度

分析算法時，存在幾種可能的考慮：

算法完成工作最少需要多少基本操作，即最優(yōu)時間復雜度

算法完成工作最多需要多少基本操作，即最壞時間復雜度

算法完成工作平均需要多少基本操作，即平均時間復雜度

對于最優(yōu)時間復雜度，其價值不大，因為它沒有提供什么有用信息，其反映的只是最樂觀最理想的情況，沒有參考價值。

對于最壞時間復雜度，提供了一種保證，表明算法在此種程度的基本操作中一定能完成工作。

對于平均時間復雜度，是對算法的一個全面評價，因此它完整全面的反映了這個算法的性質。但另一方面，這種衡量并沒有保證，不是每個計算都能在這個基本操作內(nèi)完成。而且，對于平均情況的計算，也會因為應用算法的實例分布可能并不均勻而難以計算。

因此，我們主要關注算法的最壞情況，亦即最壞時間復雜度。

時間復雜度的幾條基本計算規(guī)則基本操作，即只有常數(shù)項，認為其時間復雜度為O（1）

順序結構，時間復雜度按加法進行計算

循環(huán)結構，時間復雜度按乘法進行計算

分支結構，時間復雜度取最大值

判斷一個算法的效率時，往往只需要關注操作數(shù)量的最高次項，其它次要項和常數(shù)項可以忽略

在沒有特殊說明時，我們所分析的算法的時間復雜度都是指最壞時間復雜度

空間復雜度

類似于時間復雜度的討論，一個算法的空間復雜度S（n）定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。

漸近空間復雜度也常常簡稱為空間復雜度。

空間復雜度（SpaceComplexity）是對一個算法在運行過程中臨時占用存儲空間大小的量度。

算法的時間復雜度和空間復雜度合稱為算法的復雜度。

常見時間復雜度

｜ 執(zhí)行次數(shù)函數(shù)舉例 ｜ 階       ｜ 非正式術語 ｜

｜ ———————— ｜ ———— ｜ ————— ｜

｜ 12               ｜ O（1）     ｜ 常數(shù)階     ｜

｜ 2n＋3             ｜ O（n）     ｜ 線性階     ｜

｜ 3n2＋2n＋1         ｜ O（n2）    ｜ 平方階     ｜

｜ 5log2n＋20        ｜ O（logn）  ｜ 對數(shù)階     ｜

｜ 2n＋3nlog2n＋19    ｜ O（nlogn） ｜ nlogn階    ｜

｜ 6n3＋2n2＋3n＋4     ｜ O（n3）    ｜ 立方階     ｜

｜ 2n               ｜ O（2n）    ｜ 指數(shù)階     ｜

注意，經(jīng)常將log2n（以2為底的對數(shù)）簡寫成logn