一、如何判斷演算法的效能 ?

當同樣的問題，可以用不一樣的演算法來解決時，要如何判斷哪個演算法比較好 ?
可以使用以下兩個評量指標：

• 花的時間少，所需步驟少 ( 時間複雜度 )
• 運算時佔用的記憶體空間少 ( 空間複雜度 )

當然花的時間越少、用的記憶體越少，就是更好的演算法，而我們在討論演算法的執行時間 ( Runtime ) 時，會使用大 O 符號 ( Big O Notation ) 來表示演算法的速度。

二、演算法的執行時間與增長率

我們先透過一個情境，來了解不同演算法之間的執行時間，如何依不同的速率增長。

今天 Elaine 正在為 NASA 寫一個搜尋演算法，會在火箭快登入月球前起動，協助計算著陸地點。
Elaine 正思考要如何從簡易搜尋法跟二進位搜尋法之間做出正確的決定，這次任務的演算法要快且精準，要在 10 秒內確認著陸地點，否則火箭將偏離軌道或失事：

• 二進位搜尋法比較快
• 但簡易搜尋法比較容易撰寫，不會出錯

謹慎的 Elaine 決定用一份有 100 個元素的清單作測試，假設查一個項目耗時一毫秒：

• 簡易搜尋法：需耗費 100 毫秒
• 二進位搜尋法：需耗費 7 毫秒 ( log 100 )

Elaine 根據這次的測試結果，發現二進位搜尋法比簡易搜尋法快 15 倍。而正式清單會有 10 億個元素，二進位搜尋法大約耗費 30 毫秒，如此推算，簡易搜尋法大約會耗費 30 x 15 也就是 450 毫秒，在 10 秒內的安全範圍。

因此，Elaine 決定採用簡易搜尋法作位此次任務的演算法。但這個選擇正確嗎 ?

簡易搜尋和二進位搜尋的執行時間，並非以相同速率成長 !

用簡易搜尋法搜尋 10 億個元素，是需要花費 10 億毫秒的 ! 當搜尋次數增加時，簡易搜尋相較二進位搜尋的執行時間是大幅增加的。

三、Big O 的意義

Big O Notation 可以指出演算法的快慢，讓我們了解執行時間隨處理資料的大小所增長的幅度。舉例來說：

假設清單大小為 n。使用簡易搜尋法查找每個元素，必須操作 n 次，它的執行時間就是 O(n)

不是以秒數表達速度，而是比較操作步驟次數，代表的意涵是演算法的增長幅度。

而且 Big O 是建立在最壞情況的執行時間。以 O(n) 來說，代表的就是，簡易搜尋法的執行時間，永遠不會比 O(n) 慢。

四、常見的 Big O 執行時間

• O(1)：輸入 n ，執行步驟 1
• O(log n)：輸入 n 時，執行步驟是 log n。例如：二進位搜尋
• O(n)：執行時間隨著 n 線性增長。例如：簡易搜尋
• O(n^2)：通常這樣效能較比較差了。例如：選擇排序法、兩層 for 迴圈

原文連結：如何評估演算法的效率? Big O 與時間複雜度 - Ted's Point 泰德觀點