对数和幂的渐近复杂性
因此，显然，log(n) 是O(n)。但是，(log(n))^2 又如何呢？ sqrt(n) 或 log(n) 又如何——什么限制什么？
有一系列这样的比较：
nᵃ (vs.) (log(n))ᵇ
我经常遇到这些比较，但我从来没有想出一个好的方法来解决它们。解决一般案例的策略提示？
[编辑：我不是在谈论计算这些函数值的计算复杂性。我说的是函数本身。例如，f(n) = n 是 g(n) = log(n) 的上限，因为 f(n) ≤ cg(n)< /code> 对于 c = 1 和 n₀ > 0。]
So, clearly, log(n) is O(n). But, what about (log(n))^2? What about sqrt(n) or log(n)—what bounds what?
There's a family of comparisons like this:
nᵃ (vs.) (log(n))ᵇ
I run into these comparisons a lot, and I've never come up with a good way to solve them. Hints for tactics for solving the general case?
[EDIT: I'm not talking about the computational complexity of calculating the values of these functions. I'm talking about the functions themselves. E.g., f(n) = n is an upper bound on g(n) = log(n) because f(n) ≤ c g(n) for c = 1 and n₀ > 0.]
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对于任何正常数 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)^a is always O(n^b), for any positive constants a, b.
Are you looking for a proof? All such problems can be reduced to seeing that log(n) is O(n), by the following trick:
log(n)^a = O(n^b) is equivalent to:
log(n) = O(n^{b/a}), since raising to the 1/a power is an increasing function.
This is equivalent to
log(m^{a/b}) = O(m), by setting m = n^{b/a}.
This is equivalent to log(m) = O(m), since log(m^{a/b}) = (a/b)*log(m).
You can prove that log(n) = O(n) by induction, focusing on the case where n is a power of 2.
n^a与(log(n))^b您需要相同的底数或幂。因此，使用您的数学将
n^a更改为log(n)^（无论它得到什么来获得这个基数）或（无论它得到什么来获得这个幂） ）^b。没有一般情况n^aversus(log(n))^bYou need either bases or powers the same. So use your math to change
n^atolog(n)^(whatever it gets to get this base)or(whatever it gets to get this power)^b. There is no general case正如您关于一般情况以及您对此类问题的关注很多。这是我的建议：
使用 限制 BigO 表示法的定义，一旦您知道：
您可以使用 计算机代数系统，例如开源Maxima，这里位于有关限制的 Maxima 文档 。
有关更多详细信息和示例 - 查看此答案
As you as about general case and that you following a lot into such questions. Here is what I recommend :
Use limit definition of BigO notation, once you know:
You can use Computer Algebra System, for example opensource Maxima, here is in Maxima documentation about limits .
For more detailed info and example - check out THIS answer