增长率的顺序从小到大排序

Question

将以下函数按增长率递增的顺序排列（如果且仅当f(n)=O(g(n))时，g(n)跟随在您的列表中的f(n)后面）。

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

所以我认为答案的顺序应该是CEDAB，是否正确？我对选项A和B感到困惑。我认为选项A应该排在第一位，少一个，我的意思是请帮忙解决这个问题。这个问题是我在算法课程第一部分作业（Coursera）中遇到的。

- RV.

---

这个问题似乎与编程无关，更适合在 math.stackexchange.com 上提问。 - trincot

再想一想，那不正确。 - Henry

我认为http://cs.stackexchange.com是这种问题的最佳提问地点。 - arekolek

这个问题应该在相应的论坛中进行讨论。https://math.stackexchange.com/a/778739/473461 - Max Voitko

Answer 1

首先，任何正的 n 次方都比 log n 大，所以 E 在 C 之前，而不是之后。
另外，D 在其他所有函数之后，因为 2^n^2 的两种解释（可能是 2^(n^2) 或者 (2^n)^2 = 2^(2n)；虽然我忽略了 BIDMAS，但我可能是错的...）都是 n 本身的指数函数。
将 log 视为基数为某个任意常数 a 的对数：
a)
b)
因此，不幸的是，实际顺序取决于 a 的值，例如，如果该值为

如果大于2，则A在E之后，否则在E之前。有趣的是，E中对数项的底数是无关紧要的（它仍然保持其位置）。

- user3235832

Answer 2

答案是aecbd

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

a增长比任何其他因素都要小，特别是由于幂次中的对数项而不是项本身的原因，尤其是小于c

e是将n ** 2项乘以a得到的结果，这比它在指数中更好

b是双重指数，但仍然比二次幂更好

d显然是最糟糕的，因为它随着二次幂呈指数增长！

- Wboy