時間複雜度和空間複雜度

PS：近日，微信公众号流量主開通條件由原來的 5000 粉絲降至 500 粉絲，還記得微信的口號是：“再小的個體也有自己的品牌”，相信之前猶豫未開通公眾號的也會在今後的一段時間內開通，當然，騰訊這麼做也是因為現在的公眾號打開率非常低，而且還有面對百度、頭條等對信息流的掌控，不變是不行的。

時間複雜度和空間複雜度可以幫助我們根據具體的平台選擇合適的算法，要學會以空間換時間或以時間換空間的設計思想，如在單片機等一般是內存空間比較緊張，在追求最優算法時應該可以適當以時間來換空間進行設計，當然在大內存設備上可以選擇以空間換時間的設計思想來設計最優算法，所以，時間和空間複雜度可在一定的限制條件下作為判斷某個算法或代碼塊運行快慢的判斷方式，主要從如下幾個方面了解和學習時間和空間複雜度：

數據結構與算法關係
時間複雜度
空間複雜度
總結

數據結構與算法關係#

數據結構指一組數據的存儲結構，而算法是操作數據的一組方法，所以數據結構為算法服務，算法作用於特定的數據結構。

大 O 複雜度表示法#

大 O 複雜度表示法可以粗略的了解代碼運行的時間效率，比如下面這段代碼：

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

假如有效代碼（有賦值操作）每一行的執行時間為一個單位時間，那麼上述代碼的執行時間可表示為 2n + 2 個單位時間，這裡可以看出代碼執行時間與每行有效代碼執行的次數成正比。

如果是下面這段代碼：

 int cal(int n) {
   int sum = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum = sum +  i * j;
     }
   }
 }

在假設條件下上述代碼的執行時間可表示為 2n*n + 2n + 3，這裡也可以看出代碼執行時間與每行有效代碼執行的次數成正比，使用公式可表示為：

T(n) = O(n)

則上述兩段代碼執行時間與代碼執行次數之間的關係可以表示為：

T(n) = O(2n + 2)
T(n) = O( 2n*n + 2n + 3)

隨著數據規模的增大，後面的常數項不會影響代碼執行時間隨數據規模增長的變化趨勢，上面兩個函數很明顯一個是線性函數，一個是二次函數，隨著 n 的增大，最終二次函數的值會超過一次函數，所以我們取最高階來作比較，去除其他的次要向，簡化後如下：

T(n) = O(n)
T(n) = O(n*n)

現在就可以說上述兩段代碼的時間複雜度用大 O 表示法可表示為 O (n) 和 O (n*n)。

時間複雜度#

時間複雜度：從上面得出的結論，我們知道使用大 O 表示法表明的是該段代碼執行時間隨數據規模增大的變化趨勢，大 O 表示法的假設前提是隨著數據規模的增大，只保留最高階項就能估算代碼運行的時間複雜度，所以在進行複雜度分析時，只關注量級最大的時間複雜度即可。

常見的時間複雜度量級從小到大依次是：

常數階(O(1)) < 對數階(O(logn)) < 線性階(n) < 線性對數階(O(nlogn)) < 平方階(O(n^2)) < 立方階(O(n^3)) < 階乘階(O(n!)) < n次方階(O(n^n))

上面的量級中階乘階、次方階都屬於非多項式量級，當數據規模急劇增大時，非多項式量級算法執行時間越來越長，這種算法也是最低效的算法，下面說明一下多項式量級的注意點。

O(n)：無論有多少行代碼，只有執行次數能確定，那麼它的時間複雜度量級就表示為 O (1)，不會出現 O (2)、O (3) 等其他情況。

O(logn)：對數時間複雜度計算主要是找到滿足的條件，計算代碼運行的次數，即代碼運行多少次才能執行完，舉例如下：

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

如上述代碼，我們只要知道這段代碼執行多少次執行完就可以了，也就是找到 i 與 n 的關係，i 的值依次是 1、2、8、16 等，也就是 2^0、2^1、2^3、2^4 等，所以 i 與 n 的關係 2^t = n，然後計算出 t 的再剔除無關項的時間複雜度就是對數時間複雜度。當然線性對數階 O(nlogn) 就是將上述代碼循環 n 次的結果。

O(m+n)：如下面這段代碼在表示複雜度的時候就不能直接相加去最高階了：

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

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

  return sum_1 + sum_2;
}

m 和 n 表示兩個數據規模，我們無法確定 m 和 n 誰的量級大，此時的時間複雜度就表示為 O (m) + O (n)，如果 sum_1 * sun_2 則相應的時間複雜度表示為 O (m) * O (n)。

時間複雜度分析基本如上，下面來繼續看一下如下特殊情況複雜度分析，分析一下下面代碼的時間複雜度：

// n 表示數組 array 的長度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) pos = i;
  }
  return pos;
}

分析過程：i 和 pos 的賦值操作共 2 次，不會影響代碼執行時間隨數據規模增大的趨勢變化可忽略，在 for 循環中，如果 i 增加到 m 的時候，滿足 for 循環裡面的 if 語句中的條件，則此時的時間複雜度表示為 (1+m) n，所以該段代碼的事件複雜度一定是 O (n)，因為 if 語句在找到與 x 相等的值的時候還是沒有退出 for 循環，修改代碼如下：

// n 表示數組 array 的長度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

如果在找到數組中與 x 的值相等的值就退出循環，此時對於事件複雜度 (1+m) n 就有兩種可能，一種是能找到符合 if 語句條件的值退出循環，此時 m 一定是常量值可以忽略，此時這段代碼的複雜的就是 O (1)，當然如果已知不滿足 if 語句的判斷條件，一直循環 n 次，此時這段代碼的事件複雜度還是 O (n)，可見同一段代碼在不同的條件下可能會有不同的時間複雜度，鑑於這種情況，將時間複雜度細化為三種：

最好情況時間複雜分析：指理想情況下執行某段代碼的複雜度，對應上述代碼就是當在數組中找到滿足 if 語句條件的值的時候，上述代碼的時間複雜度就是 O (1) 就是最好時間複雜度；
最壞情況時間複雜分析：指最糟糕情況下執行某段代碼的複雜度，對應上述代碼就是永遠在數組中找不到滿足條件的退出 for 循環，此時上述代碼的時間複雜度就是 O (n) 就是最壞時間複雜度；

空間複雜度#

空間複雜度反映的是存儲空間隨數據規模增長趨勢，如下面這段代碼：

void print(int n) {
  int i = 0;//堆內存
  int[] a = new int[n];//堆內存
  for (i; i <n; ++i) {
    a[i] = i * i;
  }
}

上面代碼中關於內存申請的代碼只有兩處，其中變量 i 所占內存空間是固定的，忽略不計，其中數組的聲明申請了內存，而且大小還是 n 個 int 型所占內存的大小，所以此段代碼的空間複雜度為 O (n)。

總結#

時間複雜度反映代碼執行時間隨數據規模增長的變化趨勢，重點關注循環嵌套等，空間複雜度反映存儲空間隨數據規模增長的變化趨勢，時間複雜度相較空間複雜度更常用，開發常說的複雜度如果不指定一般說的都是時間複雜度。此外，針對一段特定代碼，還可以細化為最好情況時間複雜度、最壞情況時間複雜度、平均時間複雜度和均攤時間複雜度，分析思路基本一樣，只是限制條件不同。