我可以說Θ（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也可能有幫助。