昨天介紹怎麼計算最壞執行次數 T(n)，今天來介紹 O 表示法、Ω 表示法、Θ 表示法 這三個重要的東西。

這三個希臘字母為演算法漸進效率重要的表示法，在演算法分析至關重要

那甚麼是漸進效率呢？

我們在學習之前先來了解演算法執行時間的增長率

增長率

增長率是隨著 n 的增加，時間的增加速度，其在分析時間複雜度時是非常的因素。

以我們昨天的 insertion sort 的 T(n)

當 n 非常大的時候，係數及低次項其實對時間的其實影響不大

• 不考慮係數、低次項

所以最後只會剩下 為我們的增長率

當 n 趨近於無限時，演算法的增長率就是我們的漸進效率

O 表示法、Ω 表示法、Θ 表示法

我們先釐清一個觀念：

• Worst-Case、Average-Case、Best-Case 跟 O、Ω、Θ 並沒有直接相關

我們可以分別分析三種 case 的 O、Ω、Θ

而 O、Ω、Θ 是我們的漸進表示法

O 表示法

O（Big O）：演算法漸進的「上限」，代表一個演算法的增長率不會快過它 (<=)

• 舉 insertion sort 為例子，前面得出他最壞情況的漸進為
• 那我們可以說 insertion sort 最壞情況的時間複雜度為 (big O of )
• 我們也可以說 insertion sort 最壞情況的時間複雜度為 因為

Ω 表示法

Ω（Big Omega）：演算法漸進的「下限」，代表一個演算法的增長率至少會跟它一樣 (>=)

• 那我們可以說 insertion sort 最壞情況的時間複雜度為 (big Omega of )
• 我們也可以說 insertion sort 最壞情況的時間複雜度為 因為

Θ 表示法

Θ（Big Theta）：演算法漸進的「嚴格界限」。代表一個演算法的增長率 (==)

• 就是當 O(g(n))、Ω(g(n)) 的兩個 g(n) 相同的時候
• 以 insertion sort 為例，他們當可以說最壞情況的時間複雜度為、
• 所以我們就可以說 insertion sort 最壞情況的時間複雜度為

了解這幾個表示法後，我有了一個問題，

明明 Θ 可以描述比較精確的時間複雜度，為甚麼我們大部分看到的還是 O？

參考至 stack overflow 的網友 (網址在最後面)

假設一個很複雜的演算法，他的時間複雜度為
但要證明這個時間複雜度是正確的，需要同時證明 、 是對的
但如果我們直接證明 相對來說會容易許多
所以常常看到的時間複雜度，通常都是證明出來最小的

謝謝~

參考資料
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein，《演算法導論》，碁峰資訊，2024 年
Big O and Big Omega of worst-case time complexity (top comment)