Ham*_*aee 5 big-o big-theta asymptotic-complexity
我分析了算法和运行时间我得到Θ(n 3/2).现在我想将它与Θ(n log n)进行比较,看看它是渐近更快还是更慢,因为我这样做了:
Θ(n 3/2)=Θ(n·n 1/2)
如果我们比较它们,我们将看到我们需要比较n 1/2和log n.我检查了两者的增长情况,我发现对于较大的数字,n 1/2的增长大于log n.我能说的是n 3/2是渐近比为log N慢？
是的你可以。对于任何 ε > 0，log n = o(n ε ) （顺便说一句，这是小 o），因此 log 函数的增长速度比 n 的任何正幂都渐近慢。因此， n log n 的增长渐近地慢于 n 3/2。
希望这可以帮助！