如何衡量一個(gè)算法的快慢

數(shù)學(xué)算法俱樂部

日期?：?2021年10月03日?? ? ??

正文共?：2171字

來源?：?南方小智

??本文是一篇算法時(shí)間復(fù)雜度的入門介紹。我將逐步引出為何要使用時(shí)間復(fù)雜度來衡量一個(gè)算法的快慢，并給出時(shí)間復(fù)雜度的表示符號(hào)，介紹了最好，最壞和平均時(shí)間復(fù)雜度。

用具體的操作數(shù)來衡量

當(dāng)我們說衡量一個(gè)算法的快慢時(shí)，我們是希望找到一種方便的統(tǒng)一標(biāo)準(zhǔn)，使得對于同一個(gè)算法，我們的衡量標(biāo)準(zhǔn)不會(huì)受到一些不重要的因素影響而保持一致；對于不同的算法，我們能夠比較它們的優(yōu)劣并在實(shí)際的應(yīng)用中進(jìn)行選擇。

一個(gè)自然的想法是測量這個(gè)算法運(yùn)行所需要的時(shí)間，然后選擇跑得快的算法。但是不同的機(jī)器運(yùn)行的速度是不一樣的，一個(gè)同樣的算法在不同機(jī)器上測出來的時(shí)間可能非常不同。而且，每次想要知道一個(gè)算法的快慢如果都要在機(jī)器上通過計(jì)時(shí)來測量的話，是一件非常痛苦的事情，因?yàn)橛行┧惴赡芤淮我苌弦惶欤粋€(gè)月，甚至一個(gè)世紀(jì)。

一個(gè)有效的替代方法是通過計(jì)算一個(gè)算法用了多少次操作（或者說運(yùn)算量）來衡量它運(yùn)行的快慢，比如用了多少次加減法，乘除法，函數(shù)調(diào)用和賦值等操作。操作數(shù)越多，運(yùn)行的所需要的時(shí)間就越多。這樣的一種想法保證了我們對算法的衡量不會(huì)因?yàn)闇y試環(huán)境的變化而變化，也不用通過實(shí)際運(yùn)行來測量，只需通過計(jì)算就能得到操作數(shù)的數(shù)量。

用函數(shù)來衡量

僅僅計(jì)算操作數(shù)的一個(gè)問題是：一個(gè)固定的算法，針對不同的輸入規(guī)模，它所需要的操作數(shù)量是不一樣的。比如一個(gè)排序的算法，排100個(gè)數(shù)字和排10000個(gè)數(shù)字相比，排10000個(gè)數(shù)字所需要的運(yùn)算量會(huì)大很多。也就是，操作數(shù)是隨輸入規(guī)模變化的一個(gè)函數(shù)。

?

??所以，我們假如輸入規(guī)模是n，那么操作數(shù)就是f(n)。有時(shí)候，輸入規(guī)模不只有一個(gè)，比如關(guān)于一個(gè)矩陣的算法需要的操作數(shù)，可能和矩陣的長和寬都有關(guān)系，這時(shí)候，ff就變成了一個(gè)關(guān)于長和寬的二元函數(shù)，比如f(w,h)。這種擴(kuò)展是合理的，但是為了討論方?便，我們先只考慮規(guī)模只是一個(gè)變量n的情況。

?

f可能形式會(huì)比較復(fù)雜。比如????

那么三個(gè)函數(shù)到底誰才能代表這個(gè)算法的真正時(shí)間復(fù)雜度呢？為了滿足統(tǒng)一的衡量標(biāo)準(zhǔn)，我們必須有一個(gè)選擇方法。

??用近似函數(shù)來衡量

為了解答這個(gè)問題，我們首先要認(rèn)識(shí)到，在實(shí)踐中，我們只關(guān)心算法在輸入規(guī)模比較大的情況下的表現(xiàn)。因?yàn)楝F(xiàn)在的計(jì)算機(jī)每秒都能做上億次運(yùn)算，我們處理的實(shí)際問題也是規(guī)模比較大的。而當(dāng)輸入規(guī)模較大時(shí)，我們就可以通過只保留占最大比重的項(xiàng)，并忽略常數(shù)，來得到一個(gè)統(tǒng)一的近似函數(shù)表達(dá)式。對于上面的例子來說，近似函數(shù)就是：

我們從直觀上來理解這種近似是合理的。首先，當(dāng)數(shù)據(jù)規(guī)模nn達(dá)到十萬的時(shí)候，4n^4n2">2是40n的一萬倍，所以我們已經(jīng)沒有必要考慮40n了，我們舍棄小項(xiàng)，而只保留占最大比重的項(xiàng)。對于忽略常數(shù)，是因?yàn)椋?dāng)我們比較兩個(gè)不同的時(shí)間復(fù)雜度的時(shí)候，常數(shù)是無關(guān)緊要的：考慮兩個(gè)時(shí)間復(fù)雜度n^2和100n。100是比1大很多的，但是當(dāng)n達(dá)到十萬的時(shí)候n^2是100n的一千倍，可見常數(shù)的影響是非常小的。或者說，常數(shù)不會(huì)隨輸入規(guī)模n的變化而變化，當(dāng)輸入規(guī)模越來越大的時(shí)候，常數(shù)的影響力就越來越小。

這種機(jī)智的取舍解決了很多細(xì)節(jié)問題，比如，不同的操作可能會(huì)耗時(shí)不同，就好像加法操作要快些，乘法要慢些，除法可能更慢，而內(nèi)存的讀寫操作可能比邏輯操作更慢些。在一些要求非常精細(xì)的情況下，我們可能不得不仔細(xì)分開不同的操作，但是，在一般情況下，如果我們忽略常數(shù)造成的差異，我們可以把這些不同的操作看成是一個(gè)操作單元，也就是說，雖然乘法比加法慢了2倍，但2只是個(gè)常數(shù)，我們把這種差異忽略掉。??

??近似函數(shù)是漸近的

現(xiàn)在我們從另一個(gè)角度來理解這個(gè)近似函數(shù)。

?

當(dāng)nn不斷增大時(shí)，如果f(n)和g(n)的比值趨向于穩(wěn)定（穩(wěn)定等于一個(gè)不等于0的常數(shù)），我們就認(rèn)為f(n)和g(n)其實(shí)是漸近等價(jià)的。g(n)">g其實(shí)是漸近等價(jià)的：

由此可見，我們選取的【函數(shù)四】是和前面的三個(gè)函數(shù)在變化趨勢上是漸近的。總的來說，我們找到了一個(gè)統(tǒng)一的標(biāo)準(zhǔn)，兩個(gè)程序員的編碼風(fēng)格所造成的差別不存在了。

??表示符號(hào)

目前，我們找到了操作數(shù)關(guān)于輸入規(guī)模的一個(gè)近似函數(shù)來表示算法運(yùn)行的快慢。這個(gè)近似函數(shù)就表示了算法的時(shí)間復(fù)雜度，通常我們會(huì)說某個(gè)算法的復(fù)雜度是O(f(n))或者Θ(f(n))">Θ(f(n))。下面就說明不同的表示符號(hào)代表的含義：??

??
很多時(shí)候，我們都會(huì)使用OO符號(hào)，因?yàn)槲覀円话阒粫?huì)證明一個(gè)算法復(fù)雜度的上界（最壞情況），如果這個(gè)上界達(dá)到我們的要求了，就不必計(jì)算下界了。

這里舉一個(gè)例子，對于一個(gè)時(shí)間復(fù)雜度為n2的算法，我們可以說：

最壞，最好和平均時(shí)間復(fù)雜度

前面我們討論了算法的操作數(shù)隨輸入規(guī)模變化，但是即使是相同規(guī)模的數(shù)據(jù)，也能造成操作數(shù)的差異。這個(gè)時(shí)候，如果我們對每種可能的輸入都進(jìn)行時(shí)間復(fù)雜度的計(jì)算的話，是非常麻煩且沒有必要的。我們一般只考慮最壞，最好和平均情況下的時(shí)間復(fù)雜度：

最壞時(shí)間復(fù)雜度：在所有可能的輸入中，操作數(shù)最多的輸入的時(shí)間復(fù)雜度。
最好時(shí)間復(fù)雜度：在所有可能的輸入中，操作數(shù)最少的輸入的時(shí)間復(fù)雜度。
最壞時(shí)間復(fù)雜度：對所有可能的輸入的操作數(shù)取均值得到的時(shí)間復(fù)雜度。

這種表示時(shí)間復(fù)雜度的方法也可以運(yùn)用到空間復(fù)雜度的上，在這種復(fù)雜度的表示方法下，程序員們可以愉快地攀比誰的算法更優(yōu)，而不需要考慮實(shí)際實(shí)現(xiàn)的差異和具體運(yùn)行環(huán)境等細(xì)枝末節(jié)的東西。

—?THE END —

?行列式的導(dǎo)數(shù)

?從拉普拉斯矩陣說到譜聚類

?數(shù)據(jù)挖掘中所需的概率論與數(shù)理統(tǒng)計(jì)知識(shí)（一）

?采樣定理：有限個(gè)點(diǎn)構(gòu)建出整個(gè)函數(shù)

?這三個(gè)NLP項(xiàng)目寫進(jìn)簡歷，網(wǎng)申通過率提高50%

?比特幣的原理及運(yùn)作機(jī)制