使用 Limit 來決定 Order

Limit

1. 
2. 邏必達法則 (L’ Hospital Rule)

先備工具

常用的數學式子

1. \(\log \log n = \log (\log n)\)
2. \({\log}^kn = (\log n)^k\)
3. \(a = b^{\log_ba}\)
4. \(\log_cab = \log_ca + \log_cb\)
5. \(\log_c\frac{a}{b} = \log_ca - \log_cb\)
6. \(\log_ba^n = n\log_ba\)
7. \(\log_ba = \frac{\log_ca}{\log_cb}\)
8. \(\log_ba = \frac{1}{\log_ab}\)
9. \(\log_b\frac{1}{a} = \log_ba^{-1} = -\log_ba\)
10. \(a^{\log_bc} = c^{\log_ba}\)

練習

Note

1. Log 的底和 Complexity 無關
2. • 若 log f(n) = o(log g(n))，可保証 f(n) = o(g(n))
   • 若 log f(n) = ω(log g(n))，可保証 f(n) = ω(g(n))
   • 若 log f(n) = θ(log g(n))，不可保証 f(n) = θ(g(n))

     

3. 兩函數的 Complexity 有可能無法比較 (Ex: 週期函數)

參考資料

國立聯合大學陳士杰資料結構