给定函数的增长顺序

Question

我尝试按渐近增长顺序对这些函数进行排序，想知道我是否走在正确的轨道上。

1. 5000log2(n)
2. 平方（n）+7
3. 8n
4. n/log2(n)
5. 4nlog2(n)
6. n^1/100
7. 1/4 n^2 - 10000n .

Answer 1

上面的列表是-
1) 5000log2(n)
2) n^(1/100)
3)平方(n)+7
4)n/log2(n)
5)8n
6)4nlog2(n)
7)1/4n^2-10000n

据我所知。
有关该主题的更多信息，您可以查看 O(n)、Big-theta n 和 Omega - n

的定义

欢迎对以上列表进行更正

Answer 2

您可以通过检查 if

来测试 f(n) 是否渐近大于 g(n)

lim  f(n) / g(n) = ∞
n->∞

如果极限是一个非零常数，f(n)和g(n)渐近相等。如果为零，f(n) 渐近小于 g(n).

所以。您列表的主要部分看起来是正确的。不过还是有一些错误。

n/log2(n) 应该在 sqrt(n) + 7 和 8n 之间。

n^(1/100) 是 n 的第 100 次根，应该在平方根之前。