算法复杂度,log ^ kn vs n log n
Gui*_*lem 3 algorithm complexity-theory big-o big-theta asymptotic-complexity
我正在开发一些占用O(log ^ 3 n)的算法.(注意:把O视为大Theta,虽然Big O也会很好)
我不确定,而O(log ^ 3 n),甚至O(log ^ 2 n),被认为是O/n(n log n)更多/更少/等于复数.
如果我要严格遵守规则,我会说O(n log n)是更复杂的规则,但我仍然没有任何线索,为什么或如何.
我已经做了一些研究但是我找不到这个问题的答案.
非常感谢你.
如果将两个函数一起绘制,则可以看到n log(n)的增长速度比log 3 n快.
为了证明这一点,你需要证明ñ日志ñ >日志3 ñ对于所有值ň比一些任意数量更大Ç.找到这样一个c,你就有了证据.
实际上,对于正x,n log(n)比任何log x n增长得更快.
