單一個界並不是完整的故事
在上一篇指南中，我們用 大O符號 為執行時間蓋上一層天花板：T(n) = O(f(n)) 保證當 n 夠大時，T 永遠不會爬到某個 f 的常數倍之上。這確實有用，但它只描述了一半。說「我的演算法是 O(n^2)」排除了比 n^2 還糟的災難，卻完全沒說工作量會不會其實暗地裡便宜得多。光有天花板，地板仍是隻字未提。
更糟的是，大O符號樂於鬆散。一個真正以 Theta(n) 時間執行的演算法，同時也正確地是 O(n^2)、O(n^3) 甚至 O(2^n)——這些每一個都是有效（雖然無用）的上界，因為真正的天花板可以遠遠高懸於實際成本之上。所以當有人只回報一個大O時，你無法判斷他們究竟釘準了成長，還是只說了個安全又寬鬆的東西。要把執行時間釘死，我們需要一個從下方往上推的工具。
Omega：成長之下的地板
大Omega符號 是大O符號的鏡像。我們寫 T(n) = Omega(g(n))，意思是當 n 夠大時，T 至少是 g 的某個常數倍——執行時間永遠跌不破那層地板。形式上它沿用完全相同的 見證常數 概念，只是把不等號翻轉：存在常數 c > 0 與 n0，使得對所有 n >= n0 都有 T(n) >= c * g(n)。大O用 T(n) <= c * f(n) 從上方框住你；Omega 則從下方框住你。
一個具體的畫面：掃描一個未排序的陣列以找出最大值，必須至少看過每個元素一次，所以它的執行時間是 Omega(n)。無論你多聰明，都無法在只檢視一半元素後就確認最大值——你跳過的那個可能正是最大的。那個 Omega(n) 是關於無法迴避的工作量的陳述，這正是下界為何感覺與上界不同的原因：上界是對某一個演算法的承諾，而下界往往訴說著任何誠實的方法都必須付出的代價。
Theta：被兩側夾住
當天花板與地板形狀相同時，它們把執行時間困在一條走廊裡——那就是 Theta（漸進緊界）。我們寫 T(n) = Theta(g(n))，意思是 T(n) = O(g(n)) 而且 同時 T(n) = Omega(g(n))。展開來看，存在正常數 c1、c2 與門檻 n0，使得對所有 n >= n0 都有 c1 * g(n) <= T(n) <= c2 * g(n)。函數 T 被夾在兩條平行的 g 副本之間，既不向上也不向下逃脫，所以 g 在常數倍的意義下捕捉了它真正的成長率。
Theta 是最誠實、資訊量最大的判決，也是你應該追求的目標。考慮用一個迴圈把 1 到 n 的數字加總：每次迭代花費有限的工作量，而你恰好跑 n 次，所以成本至多是 c2 * n（O(n) 的天花板）且至少是 c1 * n（Omega(n) 的地板）。兩半都成立，所以這個迴圈是 Theta(n)——而非僅僅是 O(n^2)，也非僅僅是 Omega(1)。當 O 與 Omega 在同一個 g 上會合時，你學到的是成長本身，而不只是一個安全的界。
嚴格的表親：小o與小omega
大O與大Omega 容許界是緊的：n 是 O(n) 同時也是 Omega(n)，成長相等是被允許的。它們的小寫表親則禁止這種貼合。小o符號，寫作 T(n) = o(g(n))，說的是 T 嚴格地 比 g 成長得慢——g 終究會把 T 甩開任意你想要的倍數。所以 n = o(n^2)，但 n 不是 o(n)，因為 n 不會把自己拉開。對稱地，小omega符號，T(n) = w(g(n))，說的是 T 嚴格地比 g 成長得快，是讓 g 被無限遠拋在下方的地板。
感受這個差異最乾淨的方式是 極限觀點。如果比值 T(n) / g(n) 隨 n 增大趨於 0，那麼 T = o(g)：g 壓倒了 T。如果比值趨於無窮，那麼 T = w(g)。而如果比值穩定趨向一個正常數——既不消失也不爆炸——那麼 T = Theta(g)，兩個函數步調一致地齊步前進。極限並非官方定義（那些常數與門檻的定義才是），但當極限存在時，它是一條快速又可靠的捷徑。
把這些界用在迴圈上
當你從真實程式碼讀出執行時間時，這些符號便發揮了價值。配套的 計算迴圈迭代次數 指南提供了操作機制；這裡談的是找界的心態。一個跑 n 次、內部工作量有限的平坦迴圈，天花板與地板都是線性的，所以它是 Theta(n)。對兩層各跑至多 n 次的 巢狀迴圈，迴圈體大約觸發 n^2 次，兩個界再次吻合——Theta(n^2)。模式是：數出迭代次數，若這個次數被同一個函數從上下兩側釘住，你就得到一個 Theta。
要當心三角形迴圈，其內層範圍取決於外層索引。如果當外層索引是 i 時內層迴圈跑 i 次，總和便是 sum from i=1 to n of i = n(n+1)/2。這是 Theta(n^2)：主導項 n^2/2 固定了成長，而常數 1/2 與低階的 n/2 正是 漸進分析要我們捨棄 的塵埃。這個迴圈體觸發的次數只有完整 n 乘 n 巢狀的一半左右，但 n^2 的一半仍是 Theta(n^2)——常數不改變類別。
- 把最內層工作執行的次數，表示成 n 的函數——一個單一數值，或像 sum from i=1 to n of i 這樣乾淨的總和。
- 用高估的方式找上界：把內層範圍以它的最大值來框住，得到一個 O(...) 的天花板。
- 用低估的方式找下界：只保留一個你能保證總是會發生的常數比例的迭代，得到一個 Omega(...) 的地板。
- 如果天花板與地板落在同一個函數 g 上，宣告 Theta(g)；如果它們不同，分別回報 O 與 Omega，並坦承這個缺口。
關於界的誠實提醒
首先，別把界的方向與最佳、最壞情況搞混。Omega 的意思是「成長的地板」；它不代表「最佳情況」。你可以談論一個演算法的 最壞情況，並用 O 從上方或用 Omega 從下方為它定界，最佳情況亦然。說「插入排序是 Omega(n)」回報的是一個對每個輸入都成立的地板（它必須掃過整個陣列），而它的最壞情況是 Theta(n^2)，在已排序輸入上的最佳情況則是 Theta(n)。界的方向與你分析的是哪種情況，是兩條互相獨立的軸。
其次，這三種符號都活在大 n 的世界裡。Theta(n^2) 這個標籤描述的是規模化，而非在每個大小下的判決：因為定義只在某個門檻 n0 之後才生效，一個是 Theta(n log n) 的演算法在小輸入上可能真的會輸給 Theta(n^2) 的演算法，那裡是隱藏常數與低階項當家作主。這不是符號的缺陷——它正是漸進觀點選擇忽略的東西，也是為何真實的函式庫即使在漸進意義上較差，仍常常為極小的子陣列切換到插入排序。
第三，缺少 Theta 本身也是資訊。如果你能證明的最佳天花板是 O(n^2)，但能證明的最佳地板只是 Omega(n)，你並沒有失敗——你誠實地定位出了一道缺口，而把它收攏（透過磨利某一側直到兩者相遇）往往正是真正的演算法洞見所在。要抵抗只因 O 是 n^2 就悄悄寫下 Theta(n^2) 的誘惑；一個 Theta 主張同時斷言了地板，而你必須真的握有它。