資料結構與算法（一）---時間空間複雜度分析

講到資料結構與算法，就一定離不開時間、空間複雜度分析。複雜度分析是整個算法學習的精髓，隻要掌握了它，資料結構和算法的内容基本上就掌握了一半。

大 O 複雜度表示法

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

我們這裡隻是粗略估計，是以可以假設每行代碼執行的時間都一樣，為 unit_time

第 2、3 行代碼分别需要 1 個 unit_time 的執行時間，第 4、5 行都運作了 n 遍，是以需要 2n*unit_time 的執行時間，是以這段代碼總的執行時間就是 *(2n+2)unit_time。可以看出來，所有代碼的執行時間 T(n) 與每行代碼的執行次數成正比。照這個分析思路，我們再來看這段代碼。

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;
     }
   }
 }
           

時間複雜度分析

1. 隻關注循環執行次數最多的一段代碼
2. 加法法則：總複雜度等于量級最大的那段代碼的複雜度
3. 乘法法則：嵌套代碼的複雜度等于嵌套内外代碼複雜度的乘積

空間複雜度分析

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

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}