1.Big O 學習筆記

學習資料來源: Master the Coding Interview: Data Structures + Algorithms

什麼是好的程式碼: 1.Readable 2.Scalable，Scalable的衡量分為:

1.空間複雜度(Space Complexity): 執行演算法花費的記憶體空間。

2.時間複雜度(Time Complexity): 執行演算法時須花費的時間。

=> Big O 用來衡量不同演算法時間複雜度，當處理的資料量持續增加時，程式執行時間增加的比率：

(1)佳: O(1)、O(log n)、O(n)

(2)可接受: O(n log n)

(3)差: O(n ^ 2)、O(2 ^ n)、O*(n!)

【Big O Cheat Sheet】

• O(1) Constant- 沒有迴圈，執行時間不會隨輸入的資料量增加而增加。
• O(log N) Logarithmic- 通常出現在使用searching algorithms的情況(Binary Search)，資料經過排序(sorted)，資料可以對半處理
• O(n) Linear- 跑一次迴圈(依次處理n個項目)
• O(n log(n)) Log Linear 通常處理排序(sorting)的操作
• O(n²) Quadratic- 跑兩次迴圈，迴圈內有迴圈(nested loops)
• O(2^n) Exponential- 通常出現在使用recursive algorithms的情況
• O(n!) Factorial- 將每個元素都加上迴圈
• 遍歷一半的資料仍然是：O(n)
• 處理兩個獨立的資料：O(a * b)

範例

【Big O Rule Book】

1.Worst Case 最糟情況執行次數

2.Remove Constant 去除常數，如：O(n/2 + 1) -> O(n)

3.Different terms for inputs 分別計算不同輸入資料，如：O(n + n)、O(n * n)

(1)O(n + n): 兩筆資料在不同步驟

(2)O(n * n): 兩筆資料的步驟為巢狀關係

4.Drop Non Dominants 留下最主要影響的項目，如：O(n + n²) -> O(n²)

練習:

回到筆記列表，文章中的內容如果有誤，歡迎提醒告知，謝謝!