算法復(fù)雜度分析是整個數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，貫穿整個學(xué)科。先放一張xmind圖，用以總結(jié)

算法復(fù)雜度.png

補(bǔ)充一下常見的時間復(fù)雜度分析：

當(dāng)數(shù)據(jù)規(guī)模n越來越大時，非多項(xiàng)式量級算法的執(zhí)行時間會急劇增加，求解問題的執(zhí)行時間會無限增長，因此非常低效，一句話，根本不能用，因此看幾個常見的多項(xiàng)式時間復(fù)雜度

1. O(1)

int i = 5;

int a = 6;

這段代碼的時間復(fù)雜度是0(1),不是O(2)。 只要代碼執(zhí)行次數(shù)不隨著數(shù)據(jù)規(guī)模n的增加而增加，則此代碼的時間復(fù)雜度就是O(1);

2. O(long(n))、 O(nlog(n))

對數(shù)階時間復(fù)雜度非常常見，難分析

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

上面代碼的時間復(fù)雜度是㏒4(n);

變換一下

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

時間復(fù)雜度變?yōu)椹S8(n)
因?yàn)閘og之間可以互相轉(zhuǎn)換，比如 ㏒8(n) = ㏒8(4) * ㏒4(n)
而大O表示法又與常數(shù)項(xiàng)無關(guān)，因此對數(shù)階層的時間復(fù)雜度我們舍掉底數(shù)，統(tǒng)一表示為O( ㏒n)。
將上面代碼執(zhí)行n遍，就得到時間復(fù)雜度nlogn，歸并排序和快速排序的時間復(fù)雜度都是它。

3. O(m+n)、 O(m*n)
   如果一個算法的時間復(fù)雜度與兩個數(shù)據(jù)規(guī)模有關(guā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;
}

則算法復(fù)雜度為O(m+n),因?yàn)闊o法確定m與n誰更大

空間復(fù)雜度
表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。

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

上述代碼只有定義數(shù)組a時，給a分配了長度為n的空間，其他代碼不涉及存儲空間的分配，因此該代碼的空間復(fù)雜度為n

算法復(fù)雜度還分為最好情況時間復(fù)雜度、最壞情況時間復(fù)雜度、平均情況時間復(fù)雜度和均攤時間復(fù)雜度。

• 最好時間復(fù)雜
  看一個例子

int find(int array[], int n, int x){
    int pos = -1;
    for ( int i =0; i<n; i++) {
        if(array[i] == x){
            pos = i;
            break;
        }
    }
    return pos;
}

如果傳入的x恰好是數(shù)組array的第一個元素，則此時代碼執(zhí)行了一次，為最好情況時間復(fù)雜度O(1)，如果傳入的x恰好樹數(shù)組array的最后一個元素，或者根本就不在數(shù)組里，則此時情況為最壞時間復(fù)雜度O(n)。
那么平均時間復(fù)雜度怎么算呢，假設(shè)傳入的x在數(shù)組里與不在數(shù)組里的概率都為1/2,那么傳入的x在數(shù)組里的每個位置的概率就是 1/n * 1/2, 如果在第一個位置，則代碼執(zhí)行1此，如果在第二個位置，代碼執(zhí)行2次，在第n-1個位置就執(zhí)行n次， 那么一共就需要執(zhí)行

算法復(fù)雜度

平均時間復(fù)雜度全稱應(yīng)該是叫 加權(quán)平均時間復(fù)雜度或者期望時間復(fù)雜度