algorithm - 将f(n)排在g(n)之前是什么意思？

Question

刚参加了我的第一堂数据结构算法课，但我一点都不懂。给我的一个问题是:

将以下函数按升序排列；也就是说，当且仅当 𝑓(𝑛) 是 𝑂(𝑔(𝑛)) 时，𝑓(𝑛) 应该在列表中位于 𝑔(𝑛) 之前。

3^2n , 5n lg n + 20n , n^0 , 2^lg n , 16 ^lg n

那我该怎么办呢？将 n 替换为 1 并在排序之前计算出每个函数？

Answer 1

首先，我建议您去阅读有关 the big-O notation 的内容.然后，如果您查看@EugeneS 在评论中给您的链接，您会注意到:

O(n^n) > O(n!) > O(α^n) > O(n^α) > O(log(n)) > O(1)

所以让我们分解一下:

1. O(3^2n) = O(α^n)
2. O(5nlogn+20n) = O(nlogn)
3. O(n^0) = O(1)
4. O(2^logn) = O(α^logn)
5. O(16^logn) = O(α^logn)

现在你说

𝑓(𝑛) should come before 𝑔(𝑛) in your list if and only if 𝑓(𝑛) is 𝑂(𝑔(𝑛)).

现在可以安排了吗？根据你对 big-O 和上面列表的理解。正确的安排是

O(α^n) > O(α^logn) > O(α^logn) > O(nlogn) > O(1)

1 > 5 > 4 > 2 > 3

提醒自己:这确实是基础知识，而且非常重要，因此在继续学习类(class) Material 之前，请确保您了解这一点。