技術筆記 | 如何衡量一個演算法的好壞—Big O
評估一個演算法好壞的指標
Mar 18, 2023
本次的學習重點：
一、演算法（Algorithm）是什麼呢？
二、衡量一個演算法好壞的指標 — 時間複雜度、空間複雜度與 Big O的關聯
一、演算法（Algorithm）是什麼呢？
演算法（Algorithm） — A problem-solving procedure
現在不論是在新聞媒體上，經常廣泛地聽到人們使用演算法這個字眼，可能是在討論某個串流影音平台的推薦系統演算法，又或是聊到某間公司他們使用什麼樣的履歷篩選演算法來找出他們合適的人選，究竟演算法是什麼呢？
根據維基百科[1]的說法，演算法（Algorithm）是指一個被定義好的、計算機可施行其指示的有限步驟或次序，常用於計算、數據處理和自動推理。白話來說，科學家們為了解決現實生活當中面對的問題，他們運用演算法有效率地解決問題。
演算法的特性：
- Definite（描述要明瞭清楚、不能模糊不清）
- Finite（在有限的步驟當中能夠停下來）
- Effective（每個步驟有效，並且能夠被運算和執行）
- Procedure（程序）
二、衡量一個演算法好壞的指標
當我們了解完演算法後，你一定會想，若今天要解決一個問題時，當有多種演算法（方法）可以解決問題時，到底要使用哪種演算法比較好呢？
這時後我們需要一個指標來去衡量演算法的好壞[2]，其中最基本需要考量的指標是「時間」和「空間」，正是：
- 時間複雜度（ Time Complexity）
指的是電腦執行演算法所需要花費的時間成本
- 空間複雜度（ Space Complexity）
指的是會佔用掉電腦的記憶體空間成本
Big O
而在實務上，會使用來大 O 符號（Big O notation，Big O）來表示一個演算法時間複雜度的快慢[3]。
下面是常見的時間複雜度[2]：
- O(1)
當今天n輸入多大，它的執行時間都不會有影響，也是最快的演算法。
- O(n)
執行時間會跟著 n 的大小等比變多，線性增長。
- O(log n)
輸入數量 n 時，執行步驟是 log n。
- O(nlogn)
- O(n²)
- O(2^n)
而 O(n²)、O(2^n) 的執行效率偏差。
