面試必問的時間複雜度到底怎麼算

進階工程師title的我，最近琢磨着好好刷刷算法題更進階一些，然鵝，當我準備回憶大學和面試時候學的資料結構之時，我發現自己對這個算法複雜度的記憶隻有OOOOOooo

文章收錄在 GitHub

JavaKeeper ，N線網際網路開發必備技能兵器譜

算法（Algorithm）是指用來操作資料、解決程式問題的一組方法。對于同一個問題，使用不同的算法，也許最終得到的結果是一樣的，但在過程中消耗的資源和時間卻會有很大的差別。

那麼我們應該如何去衡量不同算法之間的優劣呢？

主要還是從算法所占用的「時間」和「空間」兩個次元去考量。

• 時間次元：是指執行目前算法所消耗的時間，我們通常用「時間複雜度」來描述。
• 空間次元：是指執行目前算法需要占用多少記憶體空間，我們通常用「空間複雜度」來描述。

是以，評價一個算法的效率主要是看它的時間複雜度和空間複雜度情況。然而，有的時候時間和空間卻又是「魚和熊掌」，不可兼得的，那麼我們就需要從中去取一個平衡點。

時間複雜度

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

時間頻度T(n)中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律，為此我們引入時間複雜度的概念。算法的時間複雜度也就是算法的時間度量，記作：T(n) = O(f(n))。它表示随問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間複雜度，簡稱「時間複雜度」。

這種表示方法我們稱為「 大O符号表示法 」，又稱為漸進符号，是用于描述函數漸進行為的數學符号

常見的時間複雜度量級有：

• 常數階$O(1)$
• 線性階$O(n)$
• 平方階$O(n^2)$
• 立方階$O(n^3)$
• 對數階$O(logn)$
• 線性對數階$O(nlogn)$
• 指數階$O(2^n)$

$O(1)$，表示該算法的執行時間（或執行時占用空間）總是為一個常量，不論輸入的資料集是大是小，隻要是沒有循環等複雜結構，那這個代碼的時間複雜度就都是O(1)，如：

int i = 1;
int j = 2;
int k = i + j;           

上述代碼在執行的時候，它消耗的時候并不随着某個變量的增長而增長，那麼無論這類代碼有多長，即使有幾萬幾十萬行，都可以用$O(1)$來表示它的時間複雜度。

$O(n)$，表示一個算法的性能會随着輸入資料的大小變化而線性變化，如

for (int i = 0; i < n; i++) {
     j = i;
   j++;
}           

這段代碼，for循環裡面的代碼會執行n遍，是以它消耗的時間是随着n的變化而變化的，是以這類代碼都可以用$O(n)$來表示它的時間複雜度。

$O(n²)$ 表示一個算法的性能将會随着輸入資料的增長而呈現出二次增長。最常見的就是對輸入資料進行嵌套循環。如果嵌套層級不斷深入的話，算法的性能将會變為立方階$O(n^3)$，$O(n^4)$，$O(n^k)$以此類推

for(x=1; i<=n; x++){
   for(i=1; i<=n; i++){
       j = i;
       j++;
    }
}           

$O(2^n)$，表示一個算法的性能會随着輸入資料的每次增加而增大兩倍，典型的方法就是裴波那契數列的遞歸計算實作

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}           

int i = 1;
while(i<n)
{
    i = i * 2;
}           

上面的代碼，在while循環裡面，每次都将 i 乘以 2，乘完之後，i 距離 n 就越來越近了，直到i不小于n退出。我們試着求解一下，假設循環次數為x，也就是說 2 的 x 次方等于 n，則由2^x=n得出x=log₂n。是以這個代碼的時間複雜度為$O(logn)$

線性對數階$O(nlogn) $，就是将時間複雜度為對數階$O(logn)$的代碼循環n遍的話，那麼它的時間複雜度就是 n * O(logN)，也就是了$O(nlogn)$，如下，

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}           

除此之外，其實還有平均情況複雜度、最好時間複雜度、最壞時間複雜度。。。一般沒有特殊說明的情況下，都是值最壞時間複雜度。

空間複雜度

空間複雜度（Space Complexity）是對一個算法在運作過程中臨時占用存儲空間大小的一個量度，同樣反映的是一個趨勢，一個算法所需的存儲空間用f(n)表示。S(n)=O(f(n))，其中n為問題的規模，S(n)表示空間複雜度。

一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出資料所占用的存儲空間和算法在運作過程中臨時占用的存儲空間這三個方面。

一般情況下，一個程式在機器上執行時，除了需要存儲程式本身的指令、常數、變量和輸入資料外，還需要存儲對資料操作的存儲單元。若輸入資料所占空間隻取決于問題本身，和算法無關，這樣隻需要分析該算法在實作時所需的輔助單元即可。若算法執行時所需的輔助空間相對于輸入資料量而言是個常數，則稱此算法為原地工作，空間複雜度為O(1)。當一個算法的空間複雜度與n成線性比例關系時，可表示為$0(n)$，類比時間複雜度。

空間複雜度比較常用的有：O(1)、O(n)、O(n²)

空間複雜度 $O(1)$

如果算法執行所需要的臨時空間不随着某個變量n的大小而變化，即此算法空間複雜度為一個常量，可表示為 O(1)

舉例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;           

代碼中的 i、j、m 所配置設定的空間都不随着處理資料量變化，是以它的空間複雜度 S(n) = O(1)

空間複雜度 $O(n)$

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}           

這段代碼中，第一行new了一個數組出來，這個資料占用的大小為n，這段代碼的2-6行，雖然有循環，但沒有再配置設定新的空間，是以，這段代碼的空間複雜度主要看第一行即可，即 S(n) = O(n)

複雜度速查表

來源：

https://liam.page/2016/06/20/big-O-cheat-sheet/

源位址：

https://www.bigocheatsheet.com/

圖例

大-O 複雜度曲線

抽象資料結構的操作複雜度

數組排序

圖操作

堆操作

參考

《大話資料結構》

https://zhuanlan.zhihu.com/p/50479555