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

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