數(shù)據(jù)結(jié)構(gòu)與算法是對(duì)于程序員來說是很重要的東西，可能很長(zhǎng)時(shí)間都用不到，可是用到的時(shí)候?qū)��?huì)大大提高和優(yōu)化代碼的執(zhí)行效率。

引入

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

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

窮舉法、枚舉法

這種方法最麻煩，也是最容易想到的，但是耗時(shí)會(huì)很長(zhǎng)

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

for b in range（0， 1001）：

for c in range（0， 1001）：

＃ 為了防止少寫等號(hào)導(dǎo)致代碼運(yùn)行失誤，將常量放在左邊

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（＂用時(shí)：｛｝＂．format（end＿time － start＿time））
輸出結(jié)果及耗時(shí)a， b， c： 0， 500， 500a， b， c： 200， 375， 425a， b， c： 375， 200， 425a， b， c： 500， 0， 500用時(shí)：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（＂用時(shí)：｛｝＂．format（end＿time － start＿time））＃ 耗時(shí)a， b， c： 0， 500， 500a， b， c： 200， 375， 425a， b， c： 375， 200， 425a， b， c： 500， 0， 500用時(shí)：1．1040208339691162Process finished with exit code 0算法的概念

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

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

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

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

算法的五大特性

輸入： 算法具有0個(gè)或多個(gè)輸入

輸出： 算法至少有1個(gè)或多個(gè)輸出

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

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

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

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

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

單靠時(shí)間值絕對(duì)可信嗎？

假設(shè)我們將第二次嘗試的算法程序運(yùn)行在一臺(tái)配置古老性能低下的計(jì)算機(jī)中，情況會(huì)如何？很可能運(yùn)行的時(shí)間并不會(huì)比在我們的電腦中運(yùn)行算法一的214．583347秒快多少。

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

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

時(shí)間復(fù)雜度與“大O記法”

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

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

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

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

如何理解“大O記法”

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

最壞時(shí)間復(fù)雜度

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

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

算法完成工作最多需要多少基本操作，即最壞時(shí)間復(fù)雜度

算法完成工作平均需要多少基本操作，即平均時(shí)間復(fù)雜度

對(duì)于最優(yōu)時(shí)間復(fù)雜度，其價(jià)值不大，因?yàn)樗鼪]有提供什么有用信息，其反映的只是最樂觀最理想的情況，沒有參考價(jià)值。

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

對(duì)于平均時(shí)間復(fù)雜度，是對(duì)算法的一個(gè)全面評(píng)價(jià)，因此它完整全面的反映了這個(gè)算法的性質(zhì)。但另一方面，這種衡量并沒有保證，不是每個(gè)計(jì)算都能在這個(gè)基本操作內(nèi)完成。而且，對(duì)于平均情況的計(jì)算，也會(huì)因?yàn)閼?yīng)用算法的實(shí)例分布可能并不均勻而難以計(jì)算。

因此，我們主要關(guān)注算法的最壞情況，亦即最壞時(shí)間復(fù)雜度。

時(shí)間復(fù)雜度的幾條基本計(jì)算規(guī)則基本操作，即只有常數(shù)項(xiàng)，認(rèn)為其時(shí)間復(fù)雜度為O（1）

順序結(jié)構(gòu)，時(shí)間復(fù)雜度按加法進(jìn)行計(jì)算

循環(huán)結(jié)構(gòu)，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算

分支結(jié)構(gòu)，時(shí)間復(fù)雜度取最大值

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

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

空間復(fù)雜度

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

漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。

空間復(fù)雜度（SpaceComplexity）是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度。

算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。

常見時(shí)間復(fù)雜度

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

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

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

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

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

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

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

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

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

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