所以，很明显，log(n)是O(n)。但是，怎么(log(n))^2办？sqrt(n)或者——什么log(n)限制了什么？
有一系列的比较是这样的：
nᵃ (vs.) (log(n))ᵇ
我经常遇到这些比较，但我从来没有想出解决它们的好方法。解决一般情况的策略提示？
[编辑：我不是在谈论计算这些函数值的计算复杂性。我说的是功能本身。例如，是因为for和f(n) = n的上限。]g(n) = log(n)f(n) ≤ c g(n)c = 1n₀ > 0
对于任何正常数 a、b，log(n)^a 始终为 O(n^b)。
你在找证据吗？通过以下技巧，所有此类问题都可以简化为看到 log(n) 为 O(n)：
log(n)^a = O(n^b) 等价于：log(n) = O(n^{b/a})，因为提高到 1/a 次方是一个递增函数。这等效于 log(m^{a/b}) = O(m)，通过设置 m = n^{b/a}。这等价于 log(m) = O(m)，因为 log(m^{a/b}) = (a/b)*log(m)。
您可以通过归纳证明 log(n) = O(n)，重点关注 n 是 2 的幂的情况。
log n -- O(log n)
sqrt n -- O(sqrt n)
n^2 -- O(n^2)
(log n)^2 -- O((log n)^2)
n^a相对(log(n))^b
您需要相同的基础或权力。所以用你的数学来n^a改变log(n)^(whatever it gets to get this base)or (whatever it gets to get this power)^b。没有一般情况
我经常遇到这些比较（...）解决一般情况的策略提示？
就像您对一般情况一样，并且您对此类问题进行了很多关注。这是我推荐的：
使用BigO 表示法的极限定义，一旦你知道：
f(n) = O(g(n)) iff limit (n approaches +inf) f(n)/g(n) exists and is not +inf
您可以使用计算机代数系统，例如开源Maxima，这里是关于限制的 Maxima 文档。