各位晚安
我需要一些帮助来比较大 O 和 Θ 算法。
我可以理解如何比较两个大 O，但是
在如何将大 O 与 Θ 或大 O 与 Ω 等进行比较等方面，我的理解有些困难。
我将在下面发布一些示例：
Θ(2ⁿ) vs Ο(2ⁿ)
Θ(n 0.6 ) vs Θ(n logn )
O(n) vs Ω(n⋅logn)
问问题
1407 次
1 回答
7
Θ(2^n) 与 Ο(2^n)
我有一个和大象一样大的东西[*]，还有一个不比大象大的东西。比较它们的大小。
Θ(n^0.6) 与 Θ(n^logn)
n^log n大于n^0.6，因为log n大于常数。但我懒得为他们想动物。
O(n) 与 Ω(nlogn)
我有一个不比老鼠大的东西，还有一个不比猫小的东西。比较它们的大小。
[*] 呃……因为东西和大象趋向于无穷大，它们的大小是一样的，无论如何。这个类比并不完美，但重点是 big-O 的意思是“不大于”，big-Omega 的意思是“不小于”，而 big-Theta 的意思是“既不大于也不小于” ”。“更大”和“更小”都是用相同的标准来判断的，实际上是指“f(n)在幅度上没有比常数大/小多次g(n)，足够大n”
于 2012-09-21T10:30:47.330 回答