算法：Big O Notation（大 O 符號）
簡單來說：Big O notation（大 O 符號）會告訴你一個算法它有 “多快”。
簡單查找和二分查找算法簡介
首先了解兩個最簡單的算法：簡單查找和二分查找。
假設有一個排好序的列表（例如 1 到 100，我們要找 57 這個數），我們要從中找到一個特定的元素。那麼：
-
簡單查找就是從頭挨個查找：
-
1 不對
-
2 不對
-
3 不對
-
…
-
56 不對
-
57 對了！
-
二分查找直接從中間開始查找：
-
50 小了
-
75 大了
-
63 大了
-
57 對了！
二分查找算法的視頻教程：二分查找算法視頻教程
比較兩個算法
假設我們要從 100 個數的排好序列到表裏面找到一個數：
-
使用 “簡單查找” 算法，最多需要猜 100 次才能猜對。
-
使用 “二分查找” 算法，最多需要猜 7 次即可猜對。
假設我們要從 40 億 個數的排好序的列表裏面找到一個數：
-
使用 “簡單查找” 算法，最多需要猜測 40 億次才能猜對。
-
使用 “二分查找” 算法，最多需要猜 32 次即可猜對。
所以：
-
針對 “簡單查找” 算法，它的時間是線性的，大 O 符號用 O(n) 表示。
-
針對 “二分查找” 算法，它的時間是對數性的，大 O 符號用 O(log n) 表示。
具體請看下錶：
Big O Notation（大 O 符號）
Big O Notation 所謂的會告訴你一個算法有 “多快”，並不是指它會告訴你一個算法會運行多少秒，而是會告訴你該算法需要多少 “步” 操作（Operations）。從而就可以表示隨着集合的變大，這個算法的速度如何變化。
例如：
-
簡單查找，它就是 O(n)。表示對於擁有 n 個元素的集合來說，“簡單查找” 最多需要進行 n 步操作。
-
二分查找，它是 O(log n) 。表示對於擁有 n 個元素的集合來說，“二分查找” 最多需要進行 log n 步操作。
幾種常見算法的 Big O
引用一個書上的圖片：
可以看到，針對不同的 Big O，隨着集合元素的增多，有些算法相對來說 “越來越快”，有些算法 “越來越慢”。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/syehEhiiImDY7hs5D1Ngzg