本文內(nèi)容借鑒一本我非常喜歡的書——《數(shù)據(jù)結(jié)構(gòu)與算法圖解》。學(xué)習(xí)之余，我決定把這本書精彩的部分摘錄出來與大家分享。??

?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-596601.html

寫在前面

從之前的章節(jié)中我們了解到，影響算法性能的主要因素是其所需的步數(shù)。

然而，我們不能簡單地把一個算法記為“22步算法”，把另一個算法記為“400步算法”，因為一個算法的步數(shù)并不是固定的。

以線性查找為例，它的步數(shù)等于數(shù)組的元素數(shù)量。如果數(shù)組有22個元素，線性查找就需要 22步；如果數(shù)組有 400個元素，線性查找就需要 400步。

量化線性查找效率的更準(zhǔn)確的方式應(yīng)該是：對于具有 N 個元素的數(shù)組，線性查找最多需要 N步。

為了方便表達(dá)數(shù)據(jù)結(jié)構(gòu)和算法的時間復(fù)雜度，計算機科學(xué)家從數(shù)學(xué)界借鑒了一種簡潔又通用的方式，那就是大 O 記法。

掌握了大 O記法，就掌握了算法分析的專業(yè)工具。

1.大O：數(shù)步數(shù)

為了統(tǒng)一描述，大 O不關(guān)注算法所用的時間，只關(guān)注其所用的步數(shù)。

第 1章介紹過，數(shù)組不論多大，讀取都只需 1步。用大 O記法來表示，就是：O(1)

O(1)意味著一種算法無論面對多大的數(shù)據(jù)量，其步數(shù)總是相同的。

就像無論數(shù)組有多大，讀取元素都只要 1 步。這 1 步在舊機器上也許要花 20 分鐘，而用現(xiàn)代的硬件卻只要 1 納秒。但這兩種情況下，讀取數(shù)組都是 1步。其他也屬于 O(1)的操作還包括數(shù)組末尾的插入與刪除。之前已證明，無論數(shù)組有多大，這兩種操作都只需 1步，所以它們的效率都是O(1)。

下面研究一下大 O 記法如何描述線性查找的效率。回想一下，線性查找在數(shù)組上要逐個檢查每個格子。在最壞情況下，線性查找所需的步數(shù)等于格子數(shù)。即如前所述：對于 N個元素的數(shù)組，線性查找需要花 N步。

用大 O記法來表示，即為：O(N)

2.常數(shù)時間與線性時間

從 O(N)可以看出，大 O 記法不只是用固定的數(shù)字（如 22、440）來表示算法的步數(shù)，而是基于要處理的數(shù)據(jù)量來描述算法所需的步數(shù)。

或者說，大 O 解答的是這樣的問題：當(dāng)數(shù)據(jù)增長時，步數(shù)如何變化？

O(N)算法所需的步數(shù)等于數(shù)據(jù)量，意思是當(dāng)數(shù)組增加一個元素時，O(N)算法就要增加 1步。而 O(1)算法無論面對多大的數(shù)組，其步數(shù)都不變。

當(dāng)數(shù)據(jù)增加一個單位時，算法也隨之增加一步。也就是說，數(shù)據(jù)越多，算法所需的步數(shù)就越多。O(N)也被稱為線性時間。

相比之下，O(1)則為一條水平線，因為不管數(shù)據(jù)量是多少，算法的步數(shù)都恒定。所以，O(1)也被稱為為常數(shù)時間。

因為大 O主要關(guān)注的是數(shù)據(jù)量變動時算法的性能變化，所以，即使一個算法的恒定步數(shù)不是 1，它也可以被歸類為 O(1)。

O(1)永遠(yuǎn)比O(N)更高效，原因在于，當(dāng)元素數(shù)量無限增多時，O(N)總會在某一臨界值超過O(1)。

3.同一算法，不同場景

之前的章節(jié)我們提到，線性查找并不總是 O(N)的。當(dāng)要找的元素在數(shù)組末尾，那確實是 O(N)。但如果它在數(shù)組開頭，1步就能找到的話，那么技術(shù)上來說應(yīng)該是 O(1)。所以概括來說，線性查找的最好情況是 O(1)，最壞情況是 O(N)。

雖然大 O 可以用來表示給定算法的最好和最壞的情景，但若無特別說明，大 O 記法一般都是指最壞情況。

這種悲觀主義其實是很有用的：知道各種算法會差到什么程度，能使我們做好最壞打算，以選出最適合的算法。

4.第三種算法

上一章我們學(xué)到：在同一個有序數(shù)組里，二分查找比線性查找要快。

算法為何重要（二分查找）http://t.csdn.cn/YPs4s下面就來看看如何用大O記法描述二分查找。

二分查找的大 O記法是：O(log N)

簡單分析一下，倘若要用二分查找在含有N個元素的有序數(shù)組中查找某個元素。

二分查找的基本思想是，每次我們都能排除掉一半的數(shù)據(jù)。

所以考慮最壞情況，就是數(shù)組里沒有我們要查找的元素，那么我們每次排除一半的元素，多

少次才能全部排除（或者說只剩一個元素）呢？

答案是??。

簡單來說，O(log N)意味著該算法當(dāng)數(shù)據(jù)量翻倍時，步數(shù)加 1。

這里我們所提過的 3種時間復(fù)雜度，按照效率由高到低來排序的話，會是這樣：

O(1)<O(log N)<O(N)

現(xiàn)在回到大 O記法。當(dāng)我們說 O(log N)時，其實指的是 O(log 2 N)，不過為了方便就省略了2而已。簡單來說，O(log N)算法的步數(shù)等于二分?jǐn)?shù)據(jù)直至元素剩余 1 個的次數(shù)。

下表是 O(N)和 O(log N)的效率對比。

每次數(shù)據(jù)量翻倍時，O(N)算法的步數(shù)也跟著翻倍，O(log N)算法卻只需加 1。

總結(jié)

學(xué)會大 O記法，我們在比較算法時就有了一致的參考系。有了它，我們就可以在現(xiàn)實場景中測量各種數(shù)據(jù)結(jié)構(gòu)和算法，寫出更快的代碼，更輕松地應(yīng)對高負(fù)荷的環(huán)境。?

下一章會用一個實際的例子，讓你看到大 O記法如何幫助我們顯著地提高代碼的性能。

?

到了這里，關(guān)于『初階數(shù)據(jù)結(jié)構(gòu) ? C語言』③ - 算法分析專業(yè)工具——大O記法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！