復雜度最大的演算法

① 一文講透演算法中的時間復雜度和空間復雜度計算方式

作為一名「程序猿」，大家應該都聽過這么一句話：程序=數據結構+演算法。

這句話是由瑞士計算機科學家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年獲得圖靈獎時說的一句話，這位大佬還以這句話為名出了一本書《Algorithms + Data Structures=Programs》，從此這句話就成為了大家耳熟能詳的一句名言。

隨著時間的推移，不管這句話是不是非常准確，但至少能說明數據結構與演算法對程序來說是非常核心的基礎，如果我們想要寫出更多優秀優雅的代碼，那麼數據結構與演算法是必須要掌握好的。

很多人可能覺得，我不會演算法，代碼一樣寫得很"溜"，演算法這東西似乎用處不大。現在互聯網的發達，我們想要什麼幾乎都可以在網上找到現成的，各種框架功能十分強大，似乎看起來確實不用演算法也可以寫出「好代碼」。然而假如我們不懂演算法，比如項目中用到了排序，我們如何評估代碼的執行效率？再比如最常用的 ArrayList 和 LinkedList ，我們該如何選擇，又比如說我們需要去集合中找某一個數，又該如何寫出性能優秀的代碼呢？

同樣的代碼，如何判斷誰的代碼是優秀的代碼？可讀性，可擴展性，健壯性可能都可以用來判定，然而這些東西我覺得並不能直接體現出你代碼的優秀，因為對用戶而言，訪問你的代碼響應速度快那就是優秀的代碼，相反，動輒響應幾秒甚至更長時間的介面，恐怕就算你可讀性再好，再健壯也稱不上是好代碼。

所以說一段代碼是否優秀，最直接的判斷標准就是性能，而如果要寫出高性能的代碼，那麼就必須要了解演算法，而且拋開這個因素，但凡不想一輩子都寫 CRUD 代碼的，也需要去了解演算法，我們使用的很多框架和中間件底層都有數據結構和演算法的身影，學好演算法對我們源碼閱讀時理解其設計思想也是大有裨益的。

要說功利性的目的，那就是面試，目前很多大廠的面試，演算法基本必面，所以想進大廠的話，咱們也得好好學學演算法。

提到演算法，很多人的第一反應就是太難學了，學不會，或者說經常是看完就忘了，但是其實對於我們一個普通的開發者而言，因為並不需要我們去發明演算法，我們需要的僅僅只是去靈活的運用演算法，所以並不需要非常扎實的數據基礎，當然基本的數學常識還是要有的。

如果說需要去發明設計一款演算法，那就要去推導去證明演算法的可行性，這種是需要具有非常扎實的數學基礎的，一般人確實無法做到，然而我們普通程序員口中提到演算法無非是二分查找法，哈希演算法等，高級一點的就還有回溯，貪心，動態規劃等等，這些所謂的演算法都是已經有現成的公式了，我們要做的無非就是理解它，然後靈活的運用它。這就和我們以前學習數學公式一樣，給你一個公式，然後你去做題，做題的過程其實就是去靈活地運用這個公式。

演算法也是同理，都是有特定方法和特定思路的，我們也並不需要去推導證明這種方式為什麼可行，所以學習演算法沒有其他訣竅，就是先理解思路，然後多練，等熟練了，自然就可以靈活運用了，也不會說學了立刻就忘了。學完就忘無非兩個原因，一是沒理解，二是沒有練習鞏固。

數據結構與演算法經常是放在一起講，這兩者是沒辦法獨立的，因為演算法是為了達到某種目的的一種實現方式，而數據結構是一種載體，也就是說演算法必須依賴數據結構這種載體，否則就是空談。換句話說：數據結構是為演算法服務的，而演算法又需要作用在特定的數據結構之上。

一個演算法到底好不好，我們如何去評價？前面我們提到了，你的代碼好不好，最直觀的就是看響應速度，演算法也一樣，同樣實現一個目的（比如說排序），誰的演算法速度快，我們就可以認為誰的演算法更優，如果說兩種演算法實現的速度差不多，那麼我們還可以去評價演算法所佔用的空間，誰佔用的空間少，那麼就可以認為誰的演算法更優，這就是演算法的基礎：時間復雜度和空間復雜度。

學習演算法之前，我們必須要學會如何分析時間復雜度和空間復雜度（也就是「快」和「省」），否則自己寫出來的演算法自己都不知道演算法的效率。

接觸過演算法的都知道，演算法的時間復雜度是用大寫的「O」來表示的，比如： O(1) ， O(n) ， O(logn) ， O(nlogn) ， O(n²) 等等。

變數指的是變數，也就是一段代碼的執行時間是隨著變數的變化而變化的，而不變指的是常量，也就是不論我的變數如何改變，執行時間都不會改變。

接下來我們就實際的來分析下常用時間復雜度的例子來練習一下。

0(1) 復雜度演算法也稱之為常數階演算法。這里的 1 是用來代指常量，也就是說這個演算法的效率是固定的，無論你的數據量如何變化，效率都一樣，這種復雜度也是最優的一種演算法。

上面的示例中不論有多少行代碼，時間復雜度都是屬於常數階段。換言之：只要代碼不存在 循環 ， 遞歸 等循環類調用，不論代碼有多少行，其復雜度都是常數階。

O(n) 復雜度演算法也稱之為線性階段。比如下面這個示例我們應該怎麼分析復雜度呢？

前面常量階沒分析是因為常量階比較容易理解，接下來我們就以線性階這個為例子來分析下具體是怎麼得到的。

我們假設每一行代碼的執行時間是 T ，那麼上面這段代碼的執行復雜度是多少呢？

答案很明顯，那就是 T+n*T ，也就是 (n+1)T ，而在演算法中有一個原則，那就是常量可以被忽略，所以就得到了 nT ，換成大 O 表示法就是 O(n) 。

這只是一個簡略的計算過程，大家也不用較真說每行代碼執行時間可能不一樣之類的，也不要較真說 for 循環佔用了一行，下面的大括弧也佔用了一行，如果要較真這個，那我建議可以去想一下 1=1 為什麼等於 2 。

演算法中的復雜度反應的只是一個趨勢，這里 O(n) 反應的就是一個趨勢，也就是說隨著 n 的變化，演算法的執行時間是會降低的。

知道了上面的線性階，那麼平方階就很好理解了，雙層循環就是平方階，同理，三次循環就是立方階， k 次循環就是 k 次方階。

O(logn) 也稱之為對數階，對數階也很常見，像二分查找，二叉樹之類的問題中會見到比較多的對數階復雜度，但是對數階也是比較難理解的一種演算法復雜度。

下面我們還是來看一個例子：

這段代碼又該如何分析復雜度呢？這段代碼最關鍵的就是要分析出 while 循環中到底循環了多少次，我們觀察這個循環，發現 i 並不是逐一遞增，而是不斷地翻倍： 1->2->4->8->16->32->64 一直到等於 n 為什麼才會結束，所以我們得到了這樣的一個公式： 2^x=n 。

也就是說我們只要計算出 x 的值，就得到了循環次數，而根據高中的數學知識我們可以得到 x=log2n （ 2 在下面，是底數，試了幾種方法都打不出來，放棄了），所以根據上面線性階的分析方法，我們省略常量，就得到了示例中的演算法復雜度為 O(log2n) 。

同樣的分析方式，下面的例子，我們可以很快地分析出復雜度就為 O(log3n) ：

上面得到的 log3n 我們可以再做進一步的轉換： log3n=log32 * log2n ，而 log32 （注意這幾個地方的情況 3 是底數，在下面） 是一個常量，常量可以省略，所以也就得到了： O(log3n)=O(log2n) 。同樣的道理，不論底數是多少，其實最終都可以轉化成和 O(log2n) 相等，正因為如此，為了方便，我們演算法中通常就會省略底數，直接寫作 O(logn) 。

上面的數學公式大家如果忘了或者看不懂也沒關系，只要記住不論對數的底數是多少，我們都算作 O(logn) ，而對於一個演算法的復雜度是否是對數階，還有一個簡易的判斷方法： 當循環中下標以指定倍數形式衰減，那麼這就是一個對數階 。

如果理解了上面的對數階，那麼這種線性對數階就非常好理解了，只需要在對數階的演算法中再嵌一層循環就是線性對數階：

分析了前面這些最常用的時間復雜度，其實我們可以得到以下規律：

除了上面常用的復雜度之外，另外還有指數階，階層階，根號階等，這些接觸的相對會較少，我們就不特意做分析了，如果大家感興趣的話，可以自己去了解下。

前面我們分析的都是只有一段代碼比較復雜的情況下得到的復雜度結果，那麼假如我一個演算法中，有多段代碼都比較復雜呢？這時候復雜度該如何分析？

我們先看下面這個例子：

這個例子中有三個循環，首先第一個，是一個常量，那麼根據前面的結論，不論這個常量是多大，都屬於常量級，所以第一個循環中的復雜度為 O(1) ，第二個和第三個循環我們前面也分析過，復雜度分別為 O(n) 和 O(n²) 。

也就是這一段代碼中有三段代碼產生了三種不同復雜度，而且這三個復雜度可以很明顯得到的大小關系為： O(1)<o(n)<o(n²) span=""> </o(n)<o(n²)> ，像這種在同一個演算法中有明確大小關系的，我們就可以直接取最大值作為這個演算法的復雜度，所以這個例子中演算法的復雜度就是 O(n²) 。

接下來我們再來看一個例子：

這個例子我們同樣對三段循環分別分析可以分別得到如下復雜度： O(1) ， O(m) ， O(n) 。這時候我們只能知道 O(1) 最小可以忽略，但是後面兩個無法卻無法確定大小，所以這時候我們需要取兩段循環復雜度之和來作為演算法的復雜度，所以可以得到這個例子的演算法復雜度為： O(m+n) 。

上面分析的時間復雜度都是比較簡單的，實際演算法中可能會比示例中復雜的多，而且我們示例中只要是循環都是無腦循環，也就是一定從頭循環到尾，然而實際中我們有時候並不需要從頭循環到尾，可能中途就會結束循環，所以我們根據實際情況，又可以將時間復雜度從以下四個方面來進一步分析：

這四種類型的時間復雜度在這里只會介紹前面三種，因為第四種比較復雜，而且使用場景也非常有限，而且對於這四種復雜度的分析，大家也作為了解就可以，不敢興趣的朋友們可以跳過這一小部分，因為在絕大部分情況我們只需要分析最壞復雜度就行，也就是假設循環全部執行完畢場景下的時間復雜度。

我們通過一個例子來理解下最好時間復雜度：

這個方法就是在一個指定數組中找到指定元素的下標，找不到就返回 -1 ，這個方法比較簡單，應該比較好理解。

注意這個方法中的循環體，如果找到元素，那麼就直接返回，這就會有一個現象，那就是我這個循環體到底會循環多少次是不確定的，可能是 1 次，也可能是 n （假設數組的長度） 次，所以假如我們要找的元素就在數組中的第一個位置，那麼我循環一次就找到了，這個演算法的復雜度就是 O(1) ，這就是最好情況時間復雜度。

理解了最好時間復雜度，那麼最壞時間復雜度也很好理解了，那就是數組中不存在我要找到元素，或者說最後一個值才是我要找的元素，那麼這樣我就必須循環完整個數組，那麼時間復雜度就是 O(n) ，這也就是最壞時間復雜度。

最好時間復雜度和最壞時間復雜度畢竟只有特殊情況才會發生，概率還是相對較小，所以我們很容易就想到我們也需要有一個平均時間復雜度。

我們簡單的來分析一下，為了便於分析，我們假設一個元素在數組和不在數組中的概率都為 1/2 ，然後假如在數組在，那麼又假設元素出現在每個位置的概率也是一樣的，也就是每個位置出現元素的概率為： 1/n 。

所以最終得到的平均時間復雜度應該等於元素在數組中和元素不在數組中兩種情況相加。

因為元素在數組中的概率為 1/2 ，然後在每個位置出現的概率也為 1/n 。假如元素出現在第一個位置，復雜度為 1*(1/2n) ；假如元素出現在第二個位置，復雜度為 2 * (1/2n) ，最終得到當前場景下時間復雜度為： 1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n) =(n+1)/4。

前面已經假定了元素不在數組中的概率為 1/2 ，所以當前場景下的時間復雜度為： n * (1/2) ，因為元素不在數組中，那麼這個演算法必然會將整個循環執行完畢，也就循環是 n 次。

最後我們把兩種情況的復雜度之和相加就得到了平均時間復雜度： (n+1)/4 + n/2 = (3n+1)/4 ，最終我們將常數類的系數忽略掉，就得到了平均時間復雜度為 O(n) 。

均攤時間復雜度的演算法需要使用攤還分析法，計算方式相對有點復雜，而且使用場景很有限，本文就不做過多介紹了。

空間復雜度全稱就是漸進空間復雜度，用來表示演算法的存儲空間與數據規模之間的增長關系。和時間復雜度一樣，空間復雜度也是用大 O 進行表示。

其實學會了分析時間復雜度，那麼空間復雜度的分析就簡單了，主要就看我們在一個演算法當中到底有沒有使用到了額外的空間來進行存儲數據，然後判斷這個額外空間的大小會不會隨著 n 的變化而變化，從而得到空間復雜度。

我們來看一個給數組賦值例子，假設這就是一個演算法，我們可以來分析下這個演算法的空間復雜度：

一開始定義了一個變數，這里需要空間，但是這是一個常量級的（不隨 n 的變化而變化），然後再定義了一個數組，數組的長度為 n ，這里數組也需要佔用空間，而且數組的空間是隨著 n 的變化而變化的，其餘代碼沒有佔用額外空間，所以我們就可以認為上面示例中的空間復雜度為 O(n) 。

對於演算法的空間復雜度也可以簡單的進行總結一下：

本文主要講述了為什麼要學習演算法，也簡單減少了數據結構與演算法之間的關系，隨後主要介紹了演算法中的入門知識：時間復雜度和空間復雜度。想要學好演算法，必須要掌握如何分析一個演算法的時間復雜度和空間復雜度，只有自己會分析這兩個個衡量演算法主要性能的標准，才能更好的寫出性能優秀的演算法，同時我們也講到了最好時間復雜度，最壞時間復雜度，平均時間復雜度和均攤時間復雜度，不過這四種復雜度的計算方式大家作為了解即可，等實際確實需要使用到再來回顧也不遲。

② 演算法復雜度：時間復雜度和空間復雜度

本文部分摘抄於此
演算法復雜度分為時間復雜度和空間復雜度。
時間復雜度是指執行演算法所需要的計算工作量；
而空間復雜度是指執行這個演算法所需要的內存空間。
（演算法的復雜性體現在運行該演算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間（即寄存器）資源，因此復雜度分為時間和空間復雜度）。

一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。 一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時， T(n)/f(n) 的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作 T(n)=O(f(n)), 稱 O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。

並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。

將基本語句執行次數的數量級放入大Ο記號中。

如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。

第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο( n 2)，則整個演算法的時間復雜度為Ο(n+ n 2)=Ο( n 2)。

Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在循環語句，其時間復雜度就是Ο(1)。其中 Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3) 稱為多項式時間， 而Ο(2n)和Ο(n!)稱為指數時間 。計算機科學家普遍認為前者（即多項式時間復雜度的演算法）是有效演算法，把這類問題稱為 P（Polynomial,多項式）類問題 ，而把後者（即指數時間復雜度的演算法）稱為 NP（Non-Deterministic Polynomial, 非確定多項式）問題 。

（4）在計算演算法時間復雜度時有以下幾個簡單的程序分析法則:

(1).對於一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間

(2).對於順序結構,需要依次執行一系列語句所用的時間可採用大O下"求和法則"

求和法則:是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))

特別地, 若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))

(3).對於選擇結構,如if語句,它的主要時間耗費是在執行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間

(4).對於循環結構,循環語句的運行時間主要體現在多次迭代中執行循環體以及檢驗循環條件的時間耗費,一般可用大O下"乘法法則"

乘法法則 : 是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則T1 * T2=O(f(n) * g(n))

(5).對於復雜的演算法,可以將它分成幾個容易估算的部分,然後利用求和法則和乘法法則技術整個演算法的時間復雜度

另外還有以下2個運演算法則:(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一個正常數

（5）下面分別對幾個常見的時間復雜度進行示例說明：

(1)、O(1)

​ Temp=i; i=j; j=temp;

以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。演算法的時間復雜度為常數階，記作T(n)=O(1)。 注意：如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。

(2)、O(n2)

2.1. 交換i和j的內容

解： 因為Θ(2n2+n+1)=n2（Θ即：去低階項，去掉常數項，去掉高階項的常參得到），所以T(n)= =O(n2)；

2.2.

​

解： 語句1的頻度是n-1

一般情況下，對步進循環語句只需考慮循環體中語句的執行次數，忽略該語句中步長加1、終值判別、控制轉移等成分，當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。

(3)、O(n)

解：

(4)、O(log2n)

解：

(5)、O(n3)

解：

（5）常用的演算法的時間復雜度和空間復雜度

一個經驗規則： 其中c是一個常量，如果一個演算法的復雜度為c 、 log2n 、n 、 n log2n ,那麼這個演算法時間效率比較高 ，如果是 2n * , 3n ,n!，那麼稍微大一些的n就會令這個演算法不能動了，居於中間的幾個則差強人意。

​ 演算法時間復雜度分析是一個很重要的問題，任何一個程序員都應該熟練掌握其概念和基本方法，而且要善於從數學層面上探尋其本質，才能准確理解其內涵。

2、演算法的空間復雜度

​ 類似於時間復雜度的討論，一個演算法的空間復雜度(Space Complexity)S(n)定義為該演算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。

空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。一個演算法在計算機存儲器上所佔用的存儲空間，包括存儲演算法本身所佔用的存儲空間，演算法的輸入輸出數據所佔用的存儲空間和演算法在運行過程中臨時佔用的存儲空間這三個方面。

演算法的輸入輸出數據所佔用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本演算法的不同而改變。存儲演算法本身所佔用的存儲空間與演算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的演算法。

演算法在運行過程中臨時佔用的存儲空間隨演算法的不同而異，有的演算法只需要佔用少量的臨時工作單元，而且不隨問題規模的大小而改變，我們稱這種演算法是「就地"進行的，是節省存儲的演算法，如這一節介紹過的幾個演算法都是如此；

有的演算法需要佔用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將佔用較多的存儲單元，例如將在第九章介紹的快速排序和歸並排序演算法就屬於這種情況。

如當一個演算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個演算法的空間復雜度與以2為底的n的對數成正比時，可表示為O(log2n)；當一個演算法的空I司復雜度與n成線性比例關系時，可表示為O(n).

【1】如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。

解答：
T(n)=O(1)，
這個程序看起來有點嚇人，總共循環運行了1100次，但是我們看到n沒有?
沒。這段程序的運行是和n無關的，
就算它再循環一萬年，我們也不管他，只是一個常數階的函數

【2】當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。

該程序段中頻度最大的語句是(5)，內循環的執行次數雖然與問題規模n沒有直接關系，但是卻與外層循環的變數取值有關，而最外層循環的次數直接與n有關，因此可以從內層循環向外層分析語句(5)的執行次數：
則該程序段的時間復雜度為T(n)=O(n3/6+低次項)=O(n3)

【3】演算法的時間復雜度不僅僅依賴於問題的規模，還與輸入實例的初始狀態有關。

在數值A[0..n-1]中查找給定值K的演算法大致如下：

此演算法中的語句(3)的頻度不僅與問題規模n有關，還與輸入實例中A的各元素取值及K的取值有關:

（5）時間復雜度評價性能

有兩個演算法A1和A2求解同一問題，時間復雜度分別是T1(n)=100n2，T2(n)=5n3。
（1）當輸入量n＜20時，有T1(n)＞T2(n)，後者花費的時間較少。
（2）隨著問題規模n的增大，兩個演算法的時間開銷之比5n3/100n2=n/20亦隨著增大。
即當問題規模較大時，演算法A1比演算法A2要有效地多。它們的漸近時間復雜度O(n2)和O(n3)從宏觀上評價了這兩個演算法在時間方面的質量。

在演算法分析時，往往對演算法的時間復雜度和漸近時間復雜度不予區分，而經常是將漸近時間復雜度T(n)=O(f(n))簡稱為時間復雜度，其中的f(n)一般是演算法中頻度最大的語句頻度。

其實生活很美好，只是你想的太多了。沒有，不會，有差距很正常，因為我不會

③ 大數據最常用的演算法有哪些

奧地利符號計算研究所(Research Institute for Symbolic Computation，簡稱RISC)的Christoph Koutschan博士在自己的頁面上發布了一篇文章，提到他做了一個調查，參與者大多數是計算機科學家，他請這些科學家投票選出最重要的演算法，以下是這次調查的結果，按照英文名稱字母順序排序。

大數據等最核心的關鍵技術：32個演算法

1、A* 搜索演算法——圖形搜索演算法，從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算通過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜索演算法是最佳優先搜索的範例。

2、集束搜索(又名定向搜索，Beam Search)——最佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過，集束搜索只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。

3、二分查找(Binary Search)——在線性數組中找特定值的演算法，每個步驟去掉一半不符合要求的數據。

4、分支界定演算法(Branch and Bound)——在多種最優化問題中尋找特定最優化解決方案的演算法，特別是針對離散、組合的最優化。

5、Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。

6、數據壓縮——採取特定編碼方案，使用更少的位元組數(或是其他信息承載單元)對信息編碼的過程，又叫來源編碼。

7、Diffie-Hellman密鑰交換演算法——一種加密協議，允許雙方在事先不了解對方的情況下，在不安全的通信信道中，共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起，加密後續通訊。

8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。

9、離散微分演算法(Discrete differentiation)。

10、動態規劃演算法(Dynamic Programming)——展示互相覆蓋的子問題和最優子架構演算法

11、歐幾里得演算法(Euclidean algorithm)——計算兩個整數的最大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。

12、期望-最大演算法(Expectation-maximization algorithm，又名EM-Training)——在統計計算中，期望-最大演算法在概率模型中尋找可能性最大的參數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其最大可能估計值;第二步是最大化，最大化在第一步上求得的最大可能值來計算參數的值。

13、快速傅里葉變換(Fast Fourier transform，FFT)——計算離散的傅里葉變換(DFT)及其反轉。該演算法應用范圍很廣，從數字信號處理到解決偏微分方程，到快速計算大整數乘積。

14、梯度下降(Gradient descent)——一種數學上的最優化演算法。

15、哈希演算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程序庫，如果使用長乘法，速度太慢。該演算法發現於1962年。

18、LLL演算法(Lenstra-Lenstra-Lovasz lattice rection)——以格規約(lattice)基數為輸入，輸出短正交向量基數。LLL演算法在以下公共密鑰加密方法中有大量使用：背包加密系統(knapsack)、有特定設置的RSA加密等等。

19、最大流量演算法(Maximum flow)——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的界面有關，這就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一個流網路中的最大流。

20、合並排序(Merge Sort)。

21、牛頓法(Newton』s method)——求非線性方程(組)零點的一種重要的迭代法。

22、Q-learning學習演算法——這是一種通過學習動作值函數(action-value function)完成的強化學習演算法，函數採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。

23、兩次篩法(Quadratic Sieve)——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法(僅次於數域篩法Number Field Sieve)。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。

24、RANSAC——是「RANdom SAmple Consensus」的縮寫。該演算法根據一系列觀察得到的數據，數據中包含異常值，估算一個數學模型的參數值。其基本假設是：數據包含非異化值，也就是能夠通過某些模型參數解釋的值，異化值就是那些不符合模型的數據點。

25、RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。

26、Sch?nhage-Strassen演算法——在數學中，Sch?nhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法復雜度為：O(N log(N) log(log(N)))，該演算法使用了傅里葉變換。

27、單純型演算法(Simplex Algorithm)——在數學的優化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待最大化(或最小化)的固定線性函數。

28、奇異值分解(Singular value decomposition，簡稱SVD)——在線性代數中，SVD是重要的實數或復數矩陣的分解方法，在信號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣(以求解最小二乘法問題)、解決超定線性系統(overdetermined linear systems)、矩陣逼近、數值天氣預報等等。

29、求解線性方程組(Solving a system of linear equations)——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字信號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor演算法——應用於模式識別領域，為所有像素找出一種計算方法，看看該像素是否處於同質區域( homogenous region)，看看它是否屬於邊緣，還是是一個頂點。

31、合並查找演算法(Union-find)——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集(disjoint-set)的數據結構可以跟蹤這樣的切分方法。合並查找演算法可以在此種數據結構上完成兩個有用的操作：

查找：判斷某特定元素屬於哪個組。

合並：聯合或合並兩個組為一個組。

32、維特比演算法(Viterbi algorithm)——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。

以上就是Christoph博士對於最重要的演算法的調查結果。你們熟悉哪些演算法?又有哪些演算法是你們經常使用的?

④ 冒泡排序法的演算法復雜度！！急急急！！

選擇C。

雙層循環，內層都是n個，所以復雜度是n方。冒泡排序就是把小的元素往前調或者把大的元素往後調，比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。

所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。

(4)復雜度最大的演算法擴展閱讀：

演算法原理：

1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

3、針對所有的元素重復以上的步驟，除了最後一個。

4、持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

⑤ 從n個數中取出m個最大的最好的演算法是什麼

有很多演算法，復雜度也不盡相同。以下簡單舉幾個例子：
1. n×m遍掃描
【演算法基本描述】n×m遍掃描
【演算法思想】每次都掃描一遍數組，取出最大元素，這樣掃描m遍就能得到m個最大的數
【演算法復雜度】O(nm)

2.排序後取最大m個數
【演算法基本描述】對n個數排序，對拍完序後的序列取m個最大的數
【演算法復雜度】視排序的復雜度，一般為O(nlogn)或O(n^2)

3.最小堆
【演算法基本描述】一遍掃描+最小堆
【演算法偽代碼】
00-建立一個最小堆（優先隊列），最小堆的大小控制在m之內
01-for 每個數：
02-----if 這個數比最小堆的堆頂元素大：
03---------彈出最小堆的最小元素
04---------把這個數插入到最小堆
05-最小堆中的m個元素就是所要求的元素
06-其中最小堆的作用就是保持裡面始終有m個最大元素，且m個元素中最小的元素在堆頂。
【演算法復雜度】O(nlogm) 遍歷O(n) 最小堆O(logm)
【其他】如果要求n個數中取最小的m個，只要把演算法反一下即可

總結：當n與m差不多大時，採用復雜度較低的排序是比較可取的，因為簡單。當m<<n時，排序是很浪費時間的，因為我們不需要後(n-m)個數，所以可以採用最小堆的方法。
我不敢說我的演算法是最好的，但是它一定是一個復雜度較低的演算法。

⑥ 常見排序演算法以及對應的時間復雜度和空間復雜度

排序 ：將雜亂無章的數據，按照一定的方法進行排列的過程叫做排序。

排序大的分類可分為 內排序 和 外排序 ，不需要訪問外存就能進行排序的叫做內排序。

排序也可以分為 穩定排序 和 不穩定排序

穩定排序 ：假設在待排序的文件中，存在兩個或兩個以上的記錄具有相同的關鍵字，在用某種排序法排序後，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法是穩定的。即；若 a[i]=a[j] , a[i] 在 a[j] 之前，經過排序後 a[i] 依然在 a[j] 之前。冒泡排序、直接插入排序、二分插入排序、歸並排序，基數排序都是穩定排序。
不穩定排序 ：直接選擇排序、堆排序、快速排序、希爾排序，猴子排序。

以升序為例，比較相鄰的元素，如果第一個比第二個大，則交換他們兩個。如果兩個元素一樣大，則繼續比較下一對。所以冒泡排序是一種穩定排序。

選擇一個基準元素,通常選擇第一個元素或者最後一個元素,通過一趟掃描，將待排序列分成兩部分,一部分比基準元素小,一部分大於等於基準元素,此時基準元素在其排好序後的正確位置,然後再用同樣的方法遞歸地排序劃分的兩部分。快速排序是不穩定排序。

將序列分為兩個部分{{有序序列},{無序}}，每次處理就是將無序數列的第一個元素與有序數列的元素從後往前逐個進行比較，找出插入位置，將該元素插入到有序數列的合適位置中。如果碰到相等的元素，就會把它插入到想等元素後面，順序不會改變，所以直接插入排序是穩定排序。

在直接插入排序的基礎上，對有序序列進行劃分。例如：序列為 {{a[0]......a[i-1]},a[i]} 其中 {a[0]......a[i-1]} 為有序序列，取 a[(i-1)/2] ，將其與 a[i] 比較，即可確定 a[i] 的范圍 (a[0]...a[(i-1)/2] 或者 a[(i-1)/2]...a[i-1]) ,然後繼續在已確定的范圍內進行二分。范圍依次縮小為： 1/2、1/4、1/8、1/16...... 可快速確定a[i]應該插入的位置。二分插入排序也是穩定排序。

將整個序列分割成若干個小的子序列，每個子序列內分別進行插入排序。一般情況下步長取n/2。直到最後一次步長為1，即所有元素在一個組中進行排序。由於希爾排序是先將整個序列劃分為多個子序列進行排序，相同的元素順序在這個過程中順序可能會被打亂，所以希爾排序是不穩定排序。

從待排序的數據元素中，選出最小或最大的元素與序列第一個數交換。直到所有數據排完。直接選擇排序是不穩定排序。例如： {3，3，1} ，第一次排序就將1和第一個3交換，想等元素的順序改變了。

以n=10的一個數組49, 38, 65, 97, 26, 13, 27, 49, 55, 4為例

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。
最大堆:每個節點的值都大於等於它的孩子節點。
最小堆:每個節點的值都小於等於它的孩子節點。
最大堆第0個數據是最大數，最小堆第0個數據是最小數。
堆排序是不穩定排序

思想

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
如何將兩個有序序列合並？(升序)
{a[0]......a[i-1]},{b[0]......b[j-1]}
若 b[0]<a[0] ，取 b[0] 放入數組 c 中，然後繼續比較數組 a 和 b 中的第一個元素，直到數組 a 和 b 中最後一對元素比較完成。

思想

將數組分成二組 a , b 如果這二組組內的數據都是有序的，那麼就可以按照上述方法對這二組數據進行排序。如果這二組數據是無序的？
可以將 a , b 組各自再分成二組。遞歸操作，直到每個小組只有一個數據，每個小組只有一個元素所以我們可以認為它已經是有序序列，然後進行合並。
先分解後合並。
歸並排序是穩定排序

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。從最低位起從0-9依次掃描序列，一邊掃描一邊將掃描到的數據加到新的序列中，得到一個序列。然後比較高一位，重復上述操作，直到最高位排序完成。數列就變成一個有序序列。基數排序是穩定排序。

以全是二位數的序列舉例

無限猴子定理 :指一隻猴子隨機在打字機鍵盤上按鍵，最後必然可以打出法國國家圖書館的每本圖書。

時間復雜度最低1次，最高可執行到世界的盡頭。。。