二分查詢和大O表示法
摘要：
如果從中間值開始猜
那麼臨界點就是 99，最壞的情況下只用猜七次，50 錯，75 錯..這樣猜
那麼得出結論，對於 n 個元素，用二分查詢最多需要 log2（n） 步，簡單查詢最多需要 n 步
2^log2 （n）=n，log 叫對數運算，2^n 叫冪運算，他們...
- 如果從中間值開始猜
- 那麼臨界點就是 99，最壞的情況下只用猜七次，50 錯，75 錯..這樣猜
那麼得出結論，對於 n 個元素，用二分查詢最多需要 log2（n） 步，簡單查詢最多需要 n 步
2^log2 （n）=n，log 叫對數運算，2^n 叫冪運算，他們互為逆運算
演算法實現
注意二分查詢法必須是有序的，簡單來說就是分一半
大 O 表示法
指出的是最糟情況下的執行時間，也可以說是運算元
- 這裡用大 O 表示法討論執行時間，都是討論的最糟糕的臨界值，比如簡單查詢 100 個元素，就是要看每一個元素。二分查詢也是檢視最遠的，那麼就只用檢視 log100 個元素約為 7
- log 時間這裡的底數預設是 2，也就是預設是 log2
- 其實我們是用冪運算的眼光來看，我們求的執行時其實就是指數
概念
- 大 O 表示法指出了演算法有多快。例如，假設列表包含 n 個元素，簡單查詢需要檢查每個元素，因此需要執行 n 次查詢,執行時間位 O（n）
- O(n),單位不是秒，大 O 表示法指的並不是以秒為單位的速度，而是能夠比較運算元，它指出了演算法執行時間的增速
- 所以 n 是運算元的意思
- 談論演算法的速度，是隨著輸入的增加，其執行事件將以怎麼樣的速度增加
常見的大 O 執行時間
由快到慢的經常遇到的五種，可以自己想象一下座標系圖
- O（log n）,也叫對數時間，這樣的演算法包括二分查詢
- O(n)，線性時間，包括簡單查詢
- O(n*log n)，包括快速排序（業界俗稱快排），一種速度較快的快速排序
- O（n^ 2）,包括選擇排序，一種速度較慢的排序演算法
- O（n！），包括旅行商問題的解決方案，一種非常慢的演算法
旅行商問題
旅行商要前往 5 個城市，同時確保旅程最短，這樣它要每個城市都去，然後計算總旅程，再挑選路線最短的
- 5 個城市有 120 種不同的排列方式，因此需要 120 次操作
- 這是一個非常非常慢的演算法，但是這個問題也是電腦科學領域待解決的問題