復(fù)雜度分析（下）

+文本內(nèi)容是對王爭《數(shù)據(jù)結(jié)構(gòu)與算法之美》課程的筆記，如果有任何侵權(quán)行為畔勤，請聯(lián)系博主刪除

最好底燎、最壞時間復(fù)雜度

先給個例子:

// 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;
        }
    }
    return pos
}

按照上次的分析方法, 這段代碼的復(fù)雜度是 $O(n)$ , 其中, n代表數(shù)組的長度.

但是在數(shù)組中查找一個數(shù)據(jù), 不需要從頭到尾遍歷一遍, 在中間可能就可以提前結(jié)束循環(huán). 優(yōu)化代碼.

// 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$ , 那時間復(fù)雜度是 $O(1)$ . 但是如果數(shù)組中不存在變量 $x$ , 那時間復(fù)雜度是 $O(n)$ .

由此引入三個概念: 最好情況時間復(fù)雜度熬芜、最壞情況時間復(fù)雜度和平均情況復(fù)雜度.

最好情況時間復(fù)雜度和最壞情況時間復(fù)雜度都很好理解, 重點記錄一下平均情況時間復(fù)雜度.

平均情況時間復(fù)雜度

查找變量x在數(shù)組中的位置, 有n+1種情況: 在數(shù)組的 $0 \sim n-1$ 位置中和不在數(shù)組中. 把每種情況下, 需要遍歷的元素累加起來, 然后再除以n+1, 就可以得到需要遍歷的元素個數(shù)的平均值, 即:
$\frac{1+2+3+\cdots+n-1+n}{n+1} = \frac{n(n+3)}{2(n+1)}$
將其簡化后可得 $O(n)$ . 但是, 這個結(jié)果是有問題的, 因為每種情況出現(xiàn)的概率不一樣.

要查找的變量 $x$ , 要么在數(shù)組里, 要么不在數(shù)組里. 為了方便理解, 假設(shè)在數(shù)組中與不在數(shù)組中的概率都為 $\frac{1}{2}$ . 另外, 要查找的數(shù)據(jù)出現(xiàn)在 $0 \sim n-1$ 這 $n$ 個位置的概率也是一樣的, 為 $\frac{1}{n}$ . 所以, 根據(jù)概率乘法法則, 要查找的數(shù)據(jù)出現(xiàn)在 $0 \sim n-1$ 中任意位置的概率就是 $\frac{1}{2n}$ .

計算過程為:
$1 \times \frac{1}{2n}+2 \times \frac{1}{2n}+3\times\frac{1}{2n}+ \cdots +n \times \frac{1}{2n} + n \times \frac{1}{2} = \frac{3n+1}{4}$
這個值就是概率論中的加權(quán)平均值, 也叫作期望值, 所以平均時間復(fù)雜度的全稱應(yīng)該叫加權(quán)平均時間復(fù)雜度或者期望時間復(fù)雜度.

這段代碼的加權(quán)平均時間復(fù)雜度仍然是 $O(n)$ .

均攤時間復(fù)雜度

均攤時間復(fù)雜度, 聽起來跟平均時間復(fù)雜度有點兒像. 但是, 其應(yīng)用場景更加特殊、更加有限.

// array 表示一個長度為 n 的數(shù)組
// 代碼中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;

void insert(int val){
    if(count == array.length){
        int sum = 0;
        for(int i=0; i<array.length; ++i){
            sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
    }
    array[count] = val;
    ++count;
}

最理想的情況是, 數(shù)組中有空閑空間, 我們只需要將數(shù)據(jù)插入到數(shù)組下表為 $count$ 的位置就可以了, 所以最好情況時間復(fù)雜度為 $O(1)$ . 最壞的情況下, 數(shù)組中沒有空閑空間了, 我們需要先做一次數(shù)組的遍歷求和, 然后再將數(shù)據(jù)插入, 所以最壞情況時間復(fù)雜度為 $O(n)$ .

而平均時間復(fù)雜度是 $O(1)$ . 我們還是可以通過概率論的方法來分析.

假設(shè)數(shù)組的長度是n, 根據(jù)數(shù)據(jù)插入的位置的不同, 我們可以分為n種情況, 每種情況的時間復(fù)雜度是O(1). 除此之外, 還有一種"額外"的情況, 就是在數(shù)組沒有空閑空間時插入一個數(shù)據(jù), 這個時候的時間復(fù)雜度是O(n). 而且, 這n+1種情況發(fā)生的概率一樣, 都是\frac{1}{n+1}. 所以, 根據(jù)加權(quán)平均的計算方法, 我們求得的平均時間復(fù)雜度就是:
$1 \times \frac{1}{n+1}+1\times\frac{1}{n+1}+\cdots+1\times\frac{1}{n+1}+n\times\frac{1}{n+1} = O(1)$
其實這個例子不需要引入概率論的知識, 對比一下 $insert()$ 和 $find()$ 的例子, 就會發(fā)現(xiàn)這兩者有很大的差別.

首先, $find()$ 在極端情況下, 復(fù)雜度才為 $O(1)$ . 但 $insert()$ 在大部分情況下, 時間復(fù)雜度都為 $O(1)$ . 只有個別情況下, 復(fù)雜度才為 $O(n)$ . 這是 $insert()$ 第一個區(qū)別與 $find()$ 的地方.

第二個不同點, 對于 $insert()$ 函數(shù)來說, $O(1)$ 時間復(fù)雜度的插入和 $O(n)$ 時間復(fù)雜度的插入, 出現(xiàn)的頻率是非常有規(guī)律的, 而且有一定的前后時序關(guān)系, 一般都是一個 $O(n)$ 插入之后, 緊跟著 $n-1$ 個 $O(1)$ 的插入操作, 循環(huán)往復(fù).

針對這樣一種特殊場景的復(fù)雜度分析, 我們并不需要像之前那樣, 找出所有的輸入情況及相應(yīng)的發(fā)生概率, 然后計算加權(quán)平均值. 為此, 引入一種更加簡潔的分析方法: 攤還分析法, 通過攤還分析法得到的時間復(fù)雜度我們起了一個名字, 叫均攤時間復(fù)雜度.

針對上述例子, 每一次 $O(n)$ 的插入操作, 都會跟著 $n-1$ 次 $O(1)$ 的插入操作, 所以把耗時多的那次操作均攤到接下來的 $n-1$ 次耗時少的操作上, 均攤下來, 這一組連續(xù)的操作的均攤時間復(fù)雜度就是 $O(1)$ .

總結(jié)其應(yīng)用場景:

對一個數(shù)據(jù)結(jié)構(gòu)進行一組連續(xù)操作中, 大部分情況下時間復(fù)雜度都很低, 只有個別情況下時間復(fù)雜度比較高, 而且這些操作之間存在前后連貫的時序關(guān)系, 這個時候, 我們就可以將一組操作放在一塊兒分析, 看是否能將較高時間復(fù)雜度那次操作的耗時, 平攤到其他那些時間復(fù)雜度比較低的操作上. 而且, 能夠應(yīng)用均攤時間復(fù)雜度分析的場合, 一般均攤時間復(fù)雜度就等于最好情況時間復(fù)雜度.