增长率按增长顺序排列

Question

按增长速率的顺序排列下列函数(在列表中g(n)跟随f(n)当且仅当f(N)=O(g(N)。

a)2^log(n)  
b)2^2log(n)  
c)n^5/2  
d)2^n^2  
e)n^2 log(n) 

因此，我认为答案是按顺序递增的

是对的吗？我对选项A和B有混淆。我认为选项A应该放在第一位。少一点，我是说，所以请帮忙解决这个问题。这个问题是我在算法课程第一部分的作业中遇到的。

Answer 1

首先，n的正幂总是大于log n，所以E在C之前，而不是在C之后。

此外，D在其他函数之后出现，就像对2^n^2的解释(可能是2^(n^2)或(2^n)^2 = 2^(2n)；我忽略BIDMAS可能是错误的.)是n本身的指数。

以log作为基本a，一些任意常量：

a)

​

b)

​

因此，不幸的是，实际的顺序取决于a的值，例如，如果

​

​

大于2，则A在E之后，否则在前面。奇怪的是，E中的日志项的基础是不相关的(它仍然保持其位置)。

Answer 2

答案是aecbd

了解原因的最简单方法是创建一个具有不同值n的表，并在它们之间进行比较。但有些直觉：

a的增长比任何其他的都要小，特别是c，因为在幂中使用了日志项，而不是这个术语本身。

e是n**2项乘以in的a，这比它在指数中的情况要好。

b是一个双指数，但仍然比二次幂好。

d是最糟糕的，因为它以二次幂指数增长！