時間複雜度到底怎麼算
- 2020 年 3 月 26 日
- 筆記
高級工程師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)$，表示該演算法的執行時間（或執行時佔用空間）總是為一個常量，不論輸入的數據集是大是小，只要是沒有循環等複雜結構，那這個程式碼的時間複雜度就都是O(1)，如：
int i = 1; int j = 2; int k = i + j; 上述程式碼在執行的時候，它消耗的時候並不隨著某個變數的增長而增長，那麼無論這類程式碼有多長，即使有幾萬幾十萬行，都可以用$O(1)$來表示它的時間複雜度。
線性階$O(n)$
$O(n)$，表示一個演算法的性能會隨著輸入數據的大小變化而線性變化，如
for (int i = 0; i < n; i++) { j = i; j++; } 這段程式碼，for循環裡面的程式碼會執行n遍，因此它消耗的時間是隨著n的變化而變化的，因此這類程式碼都可以用$O(n)$來表示它的時間複雜度。
平方階$O(n^2)$
$O(n²)$ 表示一個演算法的性能將會隨著輸入數據的增長而呈現出二次增長。最常見的就是對輸入數據進行嵌套循環。如果嵌套層級不斷深入的話，演算法的性能將會變為立方階$O(n3)$，$O(n4)$，$O(n^k)$以此類推
for(x=1; i<=n; x++){ for(i=1; i<=n; i++){ j = i; j++; } } 指數階$O(2^n)$
$O(2^n)$，表示一個演算法的性能會隨著輸入數據的每次增加而增大兩倍，典型的方法就是裴波那契數列的遞歸計算實現
int Fibonacci(int number) { if (number <= 1) return number; return Fibonacci(number - 2) + Fibonacci(number - 1); } 對數階$O(logn)$
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(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
