big-o - 我可以说 Θ(n^3/2) 时间算法比 Θ(n log n) 时间算法渐近慢吗？

Question

我分析了一个算法，运行时间我得到了 Θ(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 慢吗？

Answer 1

是的你可以。对于任何 ε > 0，log n = o(n ^ε )（顺便说一下，这是 little-o），因此 log 函数的增长速度比 n 的任何正幂都慢。因此，n log n 的增长速度比 n ^3/2渐近。

希望这可以帮助！

Answer 2

If you plot the two, you see that x^(3/2) (black on plot( grows faster than x*log(x) (red on plot): http://fooplot.com/#W3sidHlwZSI6MCwiZXEiOiJ4XigzLzIpIiwiY29sb3IiOiIjMDAwMDAwIn0seyJ0eXBlIjoyLCJlcXgiOiIxNipzaW4ocyleMyIsImVxeSI6IjEzKmNvcyhzKS02KmNvcygyKnMpLTIqY29zKDMqcyktY29zKDQqcykiLCJjb2xvciI6IiNGRjAwMDAiLCJzbWluIjoiLXBpIiwic21heCI6InBpIiwic3N0ZXAiOiIuMDEifSx7InR5cGUiOjAsImVxIjoieCpsb2coeCkiLCJjb2xvciI6IiNCRjFCMUIifSx7InR5cGUiOjEwMDAsIndpbmRvdyI6WyItMjcuNDI0Mjk1Mzg0NjE1MzczIiwiMzguMTExNzA0NjE1Mzg0NTk2IiwiLTcuODczNTk5OTk5OTk5OTk5IiwiMzIuNDU2MjQ2MTUzODQ2MTQiXX1d

Answer 3

您可以通过应用L'Hôpital 规则自己证明这一点：

这也可能有帮助。