簡述

在數(shù)據(jù)結(jié)構(gòu)與算法中，“時間復雜度”表示“隨著數(shù)據(jù)規(guī)模的增長，他的增長趨勢”，而時間復雜度，通過細化，可以分為：最好時間復雜度，最壞時間復雜度，平均時間復雜度，均攤時間復雜度。前兩者分析起來較為簡單，后兩者需要稍微展開一下。

平均時間復雜度

平均時間復雜度，又稱之為“加權(quán)平均時間復雜度”，“期望時間復雜度”，為什么叫加權(quán)呢？因為，通常計算平均時間復雜度，需要將概率考慮進去，也就是，在計算平均時間復雜度的時候，需要一個“加權(quán)值”，來真正的計算平均時間復雜度。

我們以代碼為例，對平均時間復雜度進行分析：

// n 表示數(shù)組 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;
}

代碼很簡單，表示在一個數(shù)組中，找到 x 這個數(shù)，最好復雜度是 O(1), 最壞是 O(n)。

那平均復雜度是怎么計算呢？

先說簡單的平均值計算公式：

上面的代碼，所有查找 x 的時間相加：1 + 2 + 3 +······ + n + n (這個 n 表示當 x 不存在時遍歷 array 需要的次數(shù)) ， 另外，需要查找的次數(shù)為 n + 1 次，那么結(jié)果就是：

image.png

代入大 O 表達式，結(jié)果是 O(n)。

這個公式表達的是：計算所有可能出現(xiàn)的情況之和，然后除以可能出現(xiàn)的情況的次數(shù)。說白了，這是一個絕對平均的結(jié)果。表示每個結(jié)果都可能出現(xiàn) n + 1 次。

這是一個較為粗暴的假設(shè)。

如果稍微使用一個簡單的概率來計算呢？

這里有 2 個概率：

1. x 變量是否在數(shù)組中的概率，有 2 種情況—— 在與不在，所以，他的概率是 1/2.
2. x 變量出現(xiàn)在數(shù)組的概率，有n 種情況，但只會出現(xiàn)一次，所以是 1/n.

我們把兩個概率進行相乘，結(jié)果是 1/(2n). 這個數(shù)，就是“加權(quán)值”。

如何使用加權(quán)值對上面代碼的“復雜度”進行計算？

然后，我們在這公式上把 (n + 1)換成“權(quán)重”：也就是 1/2n。

結(jié)果為 3n + 1 / 4 。這個也就是“加權(quán)后的平均時間復雜度”，表示，執(zhí)行了 1 + 2 + ···· + n + n 次的“加權(quán)平均值”。

如果使用大 O 表示法，去除系數(shù)，常數(shù)，低階，那么他的最終結(jié)果就是 O(n)。

可以看到，前者使用的是分母沒有做任何權(quán)重措施，僅僅是簡單的 n + 1，而后者，我們做了簡單的權(quán)重計算，認為出現(xiàn)的概率不是 n + 1，而是 1/2n。

可以說，加權(quán)值，是為了在前者的基礎(chǔ)上，更加的準確。也就是說，要計算準確的平均時間復雜度，就需要準確的計算這個“權(quán)重值”，而權(quán)重值會受到數(shù)據(jù)范圍，數(shù)據(jù)種類影響。因此需要在實際操作中，進行調(diào)參。

簡單來說，就拿 “x 變量是否在數(shù)組中的概率” 這個值來說，不一定是 1/2 ，如果有這樣一組數(shù)據(jù){y, s, f, f, g, x, g, h}， 那么，他的概率還是 1/2嗎，實際上只有 1/8，所以，還是得根據(jù)實際情況來。

均攤時間復雜度

個人認為，均攤時間復雜度就是“平均時間復雜度” 的一個特殊版本，相對而言也比較簡單。

例如一段代碼，在 n -1 種情況下，他的復雜度是 O（1），每 n - 1 次之后，他的時間復雜度是 O(n)?？梢钥吹?，這個代碼他的最壞時間復雜度實際是固定頻率出現(xiàn)的。所以，我們可以把 O（n） 的時間復雜度均攤到其他的 O(1) 復雜度中，得到最終的結(jié)果就是 O(1).

對一個數(shù)據(jù)結(jié)構(gòu)進行一組連續(xù)操作中，大部分情況下時間復雜度都很低，只有個別情況下，復雜度很高，而且這些操作存在連貫性和規(guī)律性，那么就進行均攤。另外，一般均攤時間復雜度就是最好時間復雜度。