概念
目的 | 提供一種方式來計算演算法的效能 |
意義 | 做一件事 (完成演算法) 的 「成本」與「總數n」的關係 |
計算標的 | 步驟 |
計算特色 | 高次方 > 低次方 ( n³ +n² ⇒ n³ ) |
ㅤ | 忽略常數 ( 9×n² ⇒ n² ) |
類型分類
下方表格由快到慢排序
類型 | 意義 |
O(1) | O(n^0) | 無論資料大小如何，算法的執行時間都保持不變。這表示該操作是常數時間的，例如陣列中某個位置的直接訪問。 |
O(log n) | 算法的運行時間隨著輸入大小的增加而緩慢增長，通常出現於二分查找等算法中。 |
O(n) | 隨著資料大小的增加，算法的執行時間呈線性增長。這意味著需要對每個資料項進行處理。 |
O(n log n) | 是許多高效排序算法（如快速排序、合併排序）所使用的時間複雜度，表示時間隨著輸入大小的增長而稍微超過線性增長 |
O(n²) | 當算法中有兩層嵌套循環時，通常會出現二次方時間的複雜度。隨著資料大小的增加，算法的執行時間會以平方速率增長。 |
O(2ⁿ) | 當資料大小增加時，算法的執行時間會呈指數增長。這類算法的效能通常非常差，並且適用於較小的資料集。 |
O(n!) | 許多暴力破解的算法會有這種複雜度，通常表示算法需要探索所有可能的排列組合，這樣的增長速度非常快。 |
類型範例
O(1)
O(log n)
O(n)
O(n log n)
