什麼是大O表示法

來自專欄通俗易懂的演算法2 人贊了文章

「大O表示法」是一種特殊的表示法，指出了演算法的速度有多快。

演算法的運行時間以不同的速度增加

「演算法的運行時間以不同的速度增加」這句話應該如何理解呢？下面我們通過??來看看這句話到底想表達什麼。

小明現在需要編寫一個查找演算法，這個演算法服務於學校圖書館，目的是幫助童鞋們能夠快速的找到自己需要的書籍所在位置。

假設小明現在只會「二分查找」和「簡單查找」。一方面，二分查找的速度很快，小明必須在 10 秒鐘內找到書籍所在位置，否則童鞋們沒有更多耐心等待。另一方面，簡單查找演算法編寫起來更容易，因此出現 bug 的可能性更小。

為了檢驗這兩種演算法的耗時，小明決定計算兩種演算法在列表包含 100 個元素的情況下需要的時間。

假設檢查一個元素需要 1 毫秒。使用簡單查找時，小明必須檢查 100 個元素，因此需要 100 毫秒才能查找完畢。而使用二分查找時，只需檢查 7 個元素（log2 100大約為7），因此需要 7 毫秒就能查找完畢。然而，實際要查找的列表可能包含 10 億個元素，在這種情況下，簡單查找需要多長時間呢？二分查找又需要多長時間呢？

小明使用包含 10 億個元素的列表運行二分查找，運行時間為 30 毫秒（log2 1 000 000 000大約為30）。他心裡想，二分查找的速度大約為簡單查找的 15 倍，因為列表包含 100 個元素時，簡單查找需要 100 毫秒，而二分查找需要 7 毫秒。因此，列表包含 10 億個元素時，簡單查找需要 30 × 15 = 450 毫秒，完全符合在 10 秒內查找完畢的要求。小明決定使用簡單查找。這是正確的選擇嗎？

不是。實際上，小明錯了，而且錯得離譜。列表包含 10 億個元素時，簡單查找需要 10 億毫秒，相當於 11 天！為什麼會這樣呢？因為二分查找和簡單查找的運行時間的增速不同。

| 簡單查找 | 二分查找 | 元素個數 |

| 100 毫秒 | 7 毫秒 | 100 |

| 10 秒 | 14 毫秒 | 10 000 |

| 11 天 | 30 毫秒 | 1 000 000 000 |

隨著元素數量的增加，二分查找需要的額外時間並不多，而簡單查找需要的額外時間卻很多。因此，隨著列表的增長，二分查找的速度比簡單查找快得多。小明以為二分查找速度為簡單查找的 15 倍，這不對：列表包含 10 億個元素時，為 3300 萬倍。有鑒於此，僅知道演算法需要多長時間才能運行完畢還不夠，還需知道運行時間如何隨列表增長而增加。這正是大O表示法的用武之地。

大O表示法指出了演算法有多快。例如，假設列表包含 n 個元素。簡單查找需要檢查每個元素，因此需要執行 n 次操作。使用大O表示法，這個運行時間為 O(n)。單位秒呢？沒有！大O表示法指的並非以秒為單位的速度。大O表示法讓你能夠比較操作數，它指出了演算法運行時間的增速。

大O表示法指出了最糟糕情況下的運行時間

假設你使用簡單查找在電話簿中找人。你知道，簡單查找的運行時間為 O(n)，這意味著在最糟情況下，必須查看電話簿中的每個條目。如果要查找的是 Chars ——電話簿中的第一個人，一次就能找到，無需查看每個條目。考慮到一次就找到了 Chars，請問這種演算法的運行時間是 O(n)還是 O(1) 呢？

簡單查找的運行時間總是為 O(n)。查找 Chars 時，一次就找到了，這是最佳的情形，但大O表示法說的是最糟的情形。因此，你可以說，在最糟情況下，必須查看電話簿中的每個條目，對應的運行時間為 O(n)。這是一個保證——你知道簡單查找的運行時間不可能超過 O(n)。

說明

除最糟情況下的運行時間外，還應考慮平均情況的運行時間，這很重要。

一些常見的大O運行時間

下面按從快到慢的順序列出了你經常會遇到的5種大O運行時間。

• O (log n )，也叫對數時間 ，這樣的演算法包括二分查找。
• O (n )，也叫線性時間 ，這樣的演算法包括簡單查找。
• O (n * log n )，這樣的演算法包括快速排序——一種速度較快的排序演算法。
• O (n 2 )，這樣的演算法包括選擇排序——一種速度較慢的排序演算法。
• O (n !)，這樣的演算法包括旅行商問題的解決方案——一種非常慢的演算法。

總結

1、演算法的速度指的並非時間，而是操作數的增速。

2、談論演算法的速度時，說的是隨著輸入的增加，其運行時間將以什麼樣的速度增加。

3、演算法的運行時間用大O表示法表示。

4、O(log n) 比 O(n)快，當需要搜索的元素越多時，前者比後者快得越多。

寫在最後

歡迎加入演算法交流群討論，Q群號：855454453

http://qm.qq.com/cgi-bin/qm/qr?k=59KI0rLwd-oVG2vZL4U2Bcr-cumShP7a (二維碼自動識別)