學習算法必備：時間復雜度與空間復雜度，你了解多少
本文轉載自微信公眾號「程序新視界」，作者丑胖俠二師兄 。轉載本文請聯系程序新視界公眾號。
前言
算法(Algorithm)是指用來操作數據、解決程序問題的一組方法。算法是大廠、外企面試的必備項，也是每個高級程序員的必備技能。針對同一問題，可以有很多種算法來解決，但不同的算法在效率和占用存儲空間上的區別可能會很大。
那么，通過什么指標來衡量算法的優劣呢?其中，上面提到的效率可以用算法的時間復雜度來描述，而所占用的存儲空間可以用算法的空間復雜度來描述。
- 時間復雜度：用于評估執行程序所消耗的時間，可以估算出程序對處理器的使用程度。
- 空間復雜度：用于評估執行程序所占用的內存空間，可以估算出程序對計算機內存的使用程度。
在實踐中或面試中，我們不僅要能夠寫出具體的算法來，還要了解算法的時間復雜度和空間復雜度，這樣才能夠評估出算法的優劣。當時間復雜度和空間復雜度無法同時滿足時，還需要從中選取一個平衡點。
一個算法通常存在最好、平均、最壞三種情況，我們一般關注的是最壞情況。最壞情況是算法運行時間的上界，對于某些算法來說，最壞情況出現的比較頻繁，也意味著平均情況和最壞情況一樣差。
通常，時間復雜度要比空間復雜度更容易出問題，更多研究的是時間復雜度，面試中如果沒有特殊說明，講的也是時間復雜度。
時間復雜度
要獲得算法的時間復雜度，最直觀的想法是把算法程序運行一遍，自然可以獲得。但實踐中往往受限于測試環境、數據規模等因素，直接測試算法要么難以實現，要么誤差較大，而且理論上也沒必要對每個算法都進行一遍測試，只需要找到一種評估指標，獲得算法執行所消耗時間的基本趨勢即可。
時間頻度
通常，一個算法所花費的時間與代碼語句執行的次數成正比，算法執行語句越多，消耗的時間也就越多。我們把一個算法中的語句執行次數稱為時間頻度，記作T(n)。
漸進時間復雜度
在時間頻度T(n)中，n代表著問題的規模，當n不斷變化時，T(n)也會不斷地隨之變化。那么，如果我們想知道T(n)隨著n變化時會呈現出什么樣的規律，那么就需要引入時間復雜度的概念。
一般情況下，算法基本操作的重復執行次數為問題規模n的某個函數，也就是用時間頻度T(n)表示。如果存在某個函數f(n)，使得當n趨于無窮大時，T(n)/f(n)的極限值是不為零的常數，那么f(n)是T(n)的同數量級函數，記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復雜度，簡稱為時間復雜度。
漸進時間復雜度用大寫O表示，所以也稱作大O表示法。算法的時間復雜度函數為：T(n)=O(f(n));
T(n)=O(f(n))表示存在一個常數C，使得在當n趨于正無窮時總有 T(n) ≤ C * f(n)。簡單來說，就是T(n)在n趨于正無窮時最大也就跟f(n)差不多大。也就是說當n趨于正無窮時T(n)的上界是C * f(n)。其雖然對f(n)沒有規定，但是一般都是取盡可能簡單的函數。
常見的時間復雜度有：O(1)常數型;O(log n)對數型，O(n)線性型，O(nlog n)線性對數型，O(n2)平方型，O(n3)立方型，O(nk)k次方型，O(2n)指數型。
上圖為不同類型的函數的增長趨勢圖，隨著問題規模n的不斷增大，上述時間復雜度不斷增大，算法的執行效率越低。
常見的算法時間復雜度由小到大依次為：Ο(1)<Ο(log n)<Ο(n)<Ο(nlog n)<Ο(n2)<Ο(n3)<…<Ο(2^n)<Ο(n!)。
值得留意的是，算法復雜度只是描述算法的增長趨勢，并不能說一個算法一定比另外一個算法高效。這要添加上問題規模n的范圍，在一定問題規范范圍之前某一算法比另外一算法高效，而過了一個閾值之后，情況可能就相反了，通過上圖我們可以明顯看到這一點。這也就是為什么我們在實踐的過程中得出的結論可能上面算法的排序相反的原因。
如何推導時間復雜度
上面我們了解了時間復雜度的基本概念及表達式，那么實踐中我們怎么樣才能通過代碼獲得對應的表達式呢?這就涉及到求解算法復雜度。
求解算法復雜度一般分以下幾個步驟：
- 找出算法中的基本語句：算法中執行次數最多的語句就是基本語句，通常是最內層循環的循環體。
- 計算基本語句的執行次數的數量級：只需計算基本語句執行次數的數量級，即只要保證函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化算法分析，使注意力集中在最重要的一點上：增長率。
- 用大Ο表示算法的時間性能：將基本語句執行次數的數量級放入大Ο記號中。
其中用大O表示法通常有三種規則：
- 用常數1取代運行時間中的所有加法常數;
- 只保留時間函數中的最高階項;
- 如果最高階項存在，則省去最高階項前面的系數;
下面通過具體的實例來說明以上的推斷步驟和規則。
時間復雜度實例
常數階O(1)
無論代碼執行了多少行，只要是沒有循環等復雜結構，那這個代碼的時間復雜度就都是O(1)，如：
- int i = 1;
- int j = 2;
- int k = 1 + 2;
上述代碼執行時，單個語句的頻度均為1，不會隨著問題規模n的變化而變化。因此，算法時間復雜度為常數階，記作T(n)=O(1)。這里我們需要注意的是，即便上述代碼有成千上萬行，只要執行算法的時間不會隨著問題規模n的增長而增長，那么執行時間只不過是一個比較大的常數而已。此類算法的時間復雜度均為O(1)。
對數階O(log n)
先來看對應的示例代碼：
- int i = 1; // ①
- while (i <= n) {
- i = i * 2; // ②
- }
在上述代碼中，語句①的頻度為1，可以忽略不計。
語句②我們可以看到它是以2的倍數來逼近n，每次都乘以2。如果用公式表示就是122*2…*2 <=n，也就是說2的x次方小于等于n時會執行循環體，記作2^x <= n，于是得出x<=logn。也就是說上述循環在執行logn次之后，便結束了，因此上述代碼的時間復雜度為O(log n)。
其實上面代碼的時間復雜度公式如果精確的來講應該是：T(n) = 1 + O(log n)，但我們上面已經講到對應的原則，“只保留時間函數中的最高階項”，因此記作O(log n)。
線性階O(n)
示例代碼：
- int j = 0; // ①
- for (int i = 0; i < n; i++) { // ②
- j = i; // ③
- j++; // ④
- }
上述代碼中，語句①的頻度為1，②的頻度為n，③的頻度為n-1，④的頻度為n-1，因此整個算法可以用公式T(n)=1+n+(n-1)+(n-1)來表示。進而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1，即O(n)=3n-1，去掉低次冪和系數即O(n)=n，因此T(n)=O(n)。
在上述代碼中for循環中的代碼會執行n遍，因此它消耗的時間是隨著n的變化而成線性變化的，因此這類算法都可以用O(n)來表示時間復雜度。
線性對數階O(nlogN)
示例代碼：
- for (int m = 1; m < n; m++) {
- int i = 1; // ①
- while (i <= n) {
- i = i * 2; // ②
- }
- }
線性對數階要對照對數階 O(log n)來進行理解。上述代碼中for循環內部的代碼便是上面講到對數階，只不過在對數階的外面套了一個n次的循環，當然，它的時間復雜度就是n*O(log n)了，于是記作O(nlog n)。
平方階O(n²)
示例代碼：
- int k = 0;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- k++;
- }
- }
平方階可對照線性階來進行理解，我們知道線性階是一層for循環，記作O(n)，此時等于又嵌套了一層for循環，那么便是n * O(n)，也就是O(n * n)，即O(n^2)。
如果將外層循環中的n改為m，即：
- int k = 0;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- k++;
- }
- }
那么，對應的時間復雜度便為：O(m * n)。
同理，立方階O(n³)、K次方階O(n^k)，只不過是嵌套了3層循環、k層循環而已。
排序算法對比
上面介紹了各種示例算法的時間復雜度推理過程，對照上面的時間復雜度以及算法效率的大小，來看一下我們常見的針對排序的幾種算法的時間復雜度對比。
空間復雜度
最后，我們再了解一下空間復雜度。空間復雜度主要指執行算法所需內存的大小，用于對程序運行過程中所需要的臨時存儲空間的度量，這里的空間復雜度同樣是預估的。
程序執行除了需要存儲空間、指令、常數、變量和輸入數據外，還包括對數據進行操作的工作單元和存儲計算所需信息的輔助空間。存儲空間通常包括：指令空間(即代碼空間)、數據空間(常量、簡單變量)等所占的固定部分和動態分配、遞歸棧所需的可變空間。其中可變空間與算法有關。
一個算法所需的存儲空間用f(n)表示。S(n)=O(f(n))其中n為問題的規模，S(n)表示空間復雜度。
下面看兩個常見的空間復雜度示例：空間復雜度O(1)和O(n)。
空間復雜度 O(1)
空間復雜度為O(1)的情況的示例代碼與時間復雜度為O(1)的實例代碼一致：
- int i = 1;
- int j = 2;
- int k = 1 + 2;
上述代碼中臨時空間并不會隨著n的變化而變化，因此空間復雜度為O(1)。總結一下就是：如果算法執行所需要的臨時空間不隨著某個變量n的大小而變化，此算法空間復雜度為一個常量，可表示為 O(1)，即 S(n) = O(1)。
空間復雜度 O(n)
示例代碼：
- int j = 0;
- int[] m = new int[n];
- for (int i = 1; i <= n; ++i) {
- j = i;
- j++;
- }
上述代碼中，只有創建int數組分配空間時與n的大小有關，而for循環內沒有再分配新的空間，因此，對應的空間復雜度為S(n) = O(n)。
總結一下
本篇文章給大家講了可以通過時間復雜度和空間復雜度來衡量算法的優劣，同時用具體的實例來講解如何計算不同方法的時間復雜度和空間復雜度。當我們了解了這些基本的概念、函數、計算方法、計算規則及算法性能之后，再進行算法的學習便可以輕松預估出算法的性能等指標。
參考文獻：
https://blog.csdn.net/zolalad/article/details/11848739
https://zhuanlan.zhihu.com/p/50479555
