iT邦幫忙

2021 iThome 鐵人賽

DAY 3
0
自我挑戰組

【用 JS 學演算法】前端工程師學徒系列 第 3

【Day 03】如何評估演算法的效率? Big O 與時間複雜度

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

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

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

當然花的時間越少、用的記憶體越少,就是更好的演算法,而我們在討論演算法的執行時間 ( 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 泰德觀點


上一篇
【Day 02】認識演算法 Algorithm ( 使用 JavaScript )
下一篇
【Day 04】LeetCode:Fizz Buzz ( 用 JavaScript 學演算法 )
系列文
【用 JS 學演算法】前端工程師學徒9

尚未有邦友留言

立即登入留言