成長率的極限定義

比較兩個函數時，最快的辦法往往不是擺弄見證常數，而是看當 n 衝向無窮時它們的比值怎麼變。把 f 放分子、g 放分母，這個分數 f(n)/g(n) 所趨近的那個數，幾乎道盡了它們相對成長的一切。

以下是對照表，假設 f(n)/g(n) 在 n 趨於無窮時的極限 L 存在。若 L = 0，則 f 成長嚴格較慢，故 f = o(g)（因而 f = O(g)）。若 L 為無窮，則 f 成長嚴格較快，故 f = omega(g)（因而 f = Omega(g)）。若 L 為正的有限常數，則 f 與 g 成長同速，故 f = Theta(g)。所以單一極限就能一舉給你 o、omega 或 Theta。例如比較 f = 3n^2 與 g = n^2 得比值 3，正常數，故 3n^2 = Theta(n^2)；比較 f = n 與 g = n^2 得比值 1/n 趨於 0，故 n = o(n^2)。

兩個誠實的提醒。第一，極限必須真的存在；對振盪的函數它可能不存在，這時你得直接退回見證常數定義（大O與大Omega從不要求極限存在）。第二，計算極限可能需要微積分工具，最有用的是羅必達法則，這正是用來證明 (log n)/n 趨於 0 或 n/(2^n) 趨於 0 的方法。不過，當它適用時，極限判準是通往乾淨漸進比較的最快路徑。