演算法復雜度log

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

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

這句話是由瑞士計算機科學家尼古拉斯·沃斯（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) 。

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

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

㈡ 為什麼很多遞歸演算法的時間復雜度里都有log n

比如
for (int i=1;i<n;i*=2) ;
循環log2(n)次
根據log換底公式
最終復雜度寫成Ο(log(n))

㈢ c語言時間復雜度里的 lg n與log2 n是一樣的嗎

都是對的哦~因為實際的需要，對數的值可以根據
數量級
改變，方便統計比較為主的。當然LG
N和LOG2N數值時不等的，在你比較一類演算法的復雜度的時候，取對數的
底數
必須一樣才有可比性，所以只是方便比較用，都是正確的。

㈣ 演算法時間復雜度比較：根號n與logn相比哪個更優優多少試根據下圖猜想其演算法

米勒羅賓是logn的演算法，但是實際應用上它並不穩定，一般在范圍較大（int64范圍）才會用，一般的情況用的都是sqrt(n)的演算法，但是在需要判斷大量素數的情況下（假設判斷次數為m），一般是比較m*sqrt(n)和n的大小，如果前者小就暴力判斷，否則用篩法會更快。

然後比較，在不考慮常數的情況下是logn更優，但是演算法常數導致在數據較小的一些情況下sqrt(n)反而更快。

第一個根號n的：

#include<cmath>

inlineboolisPrime(intx){
if(x==2){returntrue;}
if(x<2){returnfalse;}
intpos=int(sqrt(x))+1;
for(inti=2;i<=pos;++i){
if(x%i==0){returnfalse;}
}
returntrue;
}

然後logn的米勒羅賓你可以看下博客網頁鏈接

然後提供一個篩法的代碼（stl版本）

#include<vector>

boolvis[MAXNUM];//MAXNUM就是最大數字
std::vector<int>primes;//儲存素數

inlinevoidgetPrimes(intmaxn){
for(inti=2;i<=maxn;++i){
if(!vis[i]){primes.push_back(i);}
for(size_tj=0;j<primes.size()&&primes[j]*i<=maxn;++j){
vis[primes[j]*i]=true;
}
}
}

實際應用一般用篩法或者sqrt(n)演算法，只有大數據才會用米勒羅賓

㈤ 時間復雜度log怎麼算

如果程序運行的規模，每執行一次的規模是按等比例規模降低的，那麼這個演算法的時間復雜度就是logn的。

㈥ 計算復雜度中的log是以多少為底

計算中log默認以10為底，也就是lg
要是表示形式是ln，就是以e為底的
其他為底的話都需要註明

㈦ 電腦編程中快速排序的時間復雜度n log n 是n*log(n)還是什麼

復雜度的表示式裡面只看冪級不看具體底數，log n跟log2n是一回事，感覺你有些概念不清的樣子，時間復雜度的n就表示演算法處理的數字個數，快速排序的時間復雜度就是n log n，快速排序10個數的時間復雜度也還是n log n，你可以說n=10，但是時間復雜度的表示式裡面要求把具體的輸入個數用n表示，因為這樣才能反映出演算法在輸入個數增加的時候運行時間相應增加的程度，也就是「時間復雜度」這個概念本身想說明的問題。

㈧ 演算法的復雜度「nlog2n」怎麼理解

不是呀，
是n*log2(n)，後面是對數，對數可以將一個很大的數變成較小的數；

㈨ 時間復雜度log是怎麼計算出的，

i每循環一次就乘了2，知道當i＞=n時循環結束，循環m次有2^m＞=n，得到m=log2n。

㈩ 演算法復雜度中n log n和n log2 n有什麼區別

沒有區別，計算機中log若不加下標默認以2為底