我可以说Θ（n^3/2）时间算法渐近地比Θ（n log n）时间算法慢吗？

Question

我分析了算法和运行时间我得到了Θ（n ^3/2）。现在我想将它与Θ比较（N log n）的，看它是否是渐进快或慢，对于我这样做：

Θ（N ^3/2）= Θ（N＆middot; ñ^1/2）

如果我们对比一下，我们会看到，我们需要比较n个^1/2和日志N。我检查了两者的增长情况，我发现对于更大数量的增长，n ^1/2大于log n。我可以说n ^3/2是渐近比log n慢吗？

Answer 1

是的，你可以对于任何ε> 0，log n = 0（n^ε）（顺便说一句，这很少），所以对数函数渐近地比n的任何正幂次增长都慢，因此n log n增长渐近超过n ^3/2慢。

希望这有助于！

Answer 2

如果您绘制了两下，你看到的x ^（3/2）（黑色阴谋（长得比X *日志（X）（在地块红色）速度快： http://fooplot.com/#W3sidHlwZSI6MCwiZXEiOiJ4XigzLzIpIiwiY29sb3IiOiIjMDAwMDAwIn0seyJ0eXBlIjoyLCJlcXgiOiIxNipzaW4ocyleMyIsImVxeSI6IjEzKmNvcyhzKS02KmNvcygyKnMpLTIqY29zKDMqcyktY29zKDQqcykiLCJjb2xvciI6IiNGRjAwMDAiLCJzbWluIjoiLXBpIiwic21heCI6InBpIiwic3N0ZXAiOiIuMDEifSx7InR5cGUiOjAsImVxIjoieCpsb2coeCkiLCJjb2xvciI6IiNCRjFCMUIifSx7InR5cGUiOjEwMDAsIndpbmRvdyI6WyItMjcuNDI0Mjk1Mzg0NjE1MzczIiwiMzguMTExNzA0NjE1Mzg0NTk2IiwiLTcuODczNTk5OTk5OTk5OTk5IiwiMzIuNDU2MjQ2MTUzODQ2MTQiXX1d

Answer 3

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

This也可能有帮助。