如何從最壞、平均、最好的情況分析復(fù)雜度?

你好，我是彤哥，一個(gè)每天爬二十六層樓還不忘讀源碼的硬核男人。

上一節(jié)，我們從事后統(tǒng)計(jì)法過(guò)渡到漸近分析法，詳細(xì)講解了如何進(jìn)行算法的復(fù)雜度分析。

但是，如果遵循嚴(yán)格的漸近分析法，需要掌握大量數(shù)學(xué)知識(shí)，這無(wú)疑給我們?cè)u(píng)估算法的優(yōu)劣帶來(lái)了很大的挑戰(zhàn)。

那么，有沒(méi)有更好地評(píng)估算法的方法呢？

答案是必然的，本節(jié)，我們就從最壞、平均、最好三種情況來(lái)分析分析復(fù)雜度。

為了便于講解，我寫(xiě)了一個(gè)小例子：

public classLinearSearch{
publicstaticvoidmain(String[] args){
int[] array = new int[]{1, 8, 9, 3, 5, 6, 10, 13};
int index = search(array, 10);
        System.out.println("index=" + index);
    }

privatestaticintsearch(int[] array, int value){
for (int i = 0; i < array.length; i++) {
if (array[i] == value) {
return i;
            }
        }
return -1;
    }
}

這個(gè)例子使用線(xiàn)性搜索從一個(gè)數(shù)組中查找一個(gè)元素，這個(gè)元素有可能存在，也有可能不存在于數(shù)組中。

在最壞情況下，要查找的元素不存在于數(shù)組中，此時(shí)，它的時(shí)間復(fù)雜度是多少呢？

很簡(jiǎn)單，必然需要遍歷完所有元素才會(huì)發(fā)現(xiàn)要查找的元素不存在于數(shù)組中。

所以，最壞情況下，使用線(xiàn)性查找的時(shí)間復(fù)雜度為O(n)。

在平均情況下，我們要照顧到每一個(gè)元素，此時(shí)，它的時(shí)間復(fù)雜度如何計(jì)算呢？

在上一節(jié)，我們已經(jīng)講過(guò)計(jì)算方式了，不過(guò)，這里考慮到有元素不存在于數(shù)組中，所以，是(n+1)種可能：

1*1/(n+1) + 2*/(n+1) + ... + n*1/(n+1) + (n+1)/(n+1) = 1/(n+1) * (n+1)(n+2)/2 = (n+2)/2

所以，在平均情況下，忽略掉常數(shù)項(xiàng)，使用線(xiàn)性查找的時(shí)間復(fù)雜度也是O(n)。

為什么要忽略掉常數(shù)項(xiàng)？

當(dāng)n趨向于無(wú)窮大的時(shí)候，常數(shù)項(xiàng)的意義不是很大，所以，可以忽略，比如(n+2)/2=n/2 + 1，n本身已經(jīng)趨向于無(wú)窮大，加不加1有什么意義呢，n的倍數(shù)是2還是1/2并不會(huì)有明顯的差別。

同樣地，低階項(xiàng)一般也會(huì)抹掉，比如2n^2 + 3n + 1，當(dāng)n趨向于無(wú)窮大的時(shí)候，n^2的值是遠(yuǎn)遠(yuǎn)大于3n的，所以，不需要保留3n。

所以，計(jì)算復(fù)雜度時(shí)通常都會(huì)把常數(shù)項(xiàng)和低階項(xiàng)抹掉，只保留高階項(xiàng)。

最好情況是什么呢？

如果我們要查找的元素正好是數(shù)組的第一個(gè)元素，查找一次就找到了，這無(wú)疑是最好的情況。

所以，在最好情況下，使用線(xiàn)性查找的時(shí)間復(fù)雜度是O(1)。

通過(guò)上面的分析，可以看到，最壞情況和最好情況是比較好評(píng)估的，而平均情況則比較難以計(jì)算。

但是，最好情況又不能代表大多數(shù)樣本，且平均情況與最壞情況在省略常數(shù)項(xiàng)的情況下往往是比較接近的。

所以，通常，我們使用最壞情況來(lái)評(píng)估算法的時(shí)間復(fù)雜度，這也是比較簡(jiǎn)單的一種評(píng)估方法，且往往也是比較準(zhǔn)確的。

本節(jié)，我們從最壞、平均、最好三種情況分析了線(xiàn)性查找的時(shí)間復(fù)雜度，經(jīng)過(guò)詳細(xì)地分析，我們得出結(jié)論，通常使用最壞情況來(lái)評(píng)估算法的時(shí)間復(fù)雜度。

請(qǐng)注意，我們這里使用了“通常”，說(shuō)明有些情況是不能使用最壞情況來(lái)評(píng)估算法的時(shí)間復(fù)雜度的。

那么，你知道什么情況下不能使用最壞情況來(lái)評(píng)估算法的時(shí)間復(fù)雜度嗎？

下一節(jié)，我們接著聊。

關(guān)注公眾號(hào)“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識(shí)！