大家晚上好
我需要一些帮助来比较大 O 和 Θ 算法。
我能理解如何比较两个大 O，但有些麻烦
我对如何比较 big-O 与 Θ 或 big-O 与 Ω 等的理解。
我将在下面发布一些示例:
Θ(2ⁿ) 与 Ο(2ⁿ)
Θ(n0.6) 与 Θ(nlogn)
O(n) 与 Ω(n⋅logn)
最佳答案
Θ(2^n) vs Ο(2^n)
我有一个和大象一样大的东西[*]，还有一个不比大象大。比较它们的尺寸。
Θ(n^0.6) vs Θ(n^logn)
n^log n 大于 n^0.6，因为 log n 大于常数。但我懒得为他们考虑动物。
O(n) vs Ω(nlogn)
我有一个不比老鼠大的东西，另一个不比猫小的东西。比较它们的大小。
[*] 呃...因为这东西和大象趋向于无穷大，所以它们的大小是一样的，无论如何。这个类比并不完美，但重点是 big-O 表示“不大于”，big-Omega 表示“不小于”，big-Theta 表示“既不大于也不小于” ”。 “大”和“小”都是用同一个标准来判断的，其实就是“f(n)的大小不大于/小于常数倍g(n)，对于足够大的 n"
关于algorithm - 比较 Big O、Theta 和 Omega 之间的算法复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12528112/