algorithm - 排序算法的上下界

Question

这是一个非常简单的问题，但我很难完全理解这个概念。

我试图理解以下语句之间的区别:

1. 存在一种算法，可以在最佳情况下以 O(n) 的时间对 n 个数字的数组进行排序。
2. 在最佳情况下，每种算法都会在 O(n) 中对 n 个数字的数组进行排序。
3. 存在一种算法，可以在最佳情况下对 Omega(n) 中的 n 个数字数组进行排序。
4. 在最佳情况下，每种算法都会对 Omega(n) 中的 n 个数字数组进行排序。

我将首先解释是什么让我发疯。我不确定 1 和 3 - 但我知道对于其中一个，答案是正确的，只需指定一个案例，而对于另一个，答案是正确的，通过检查所有可能的输入。因此，我知道其中一个必须是真的，只是通过指定数组已经排序但我不能告诉哪个。我的老师总是告诉我要考虑一下，就像我们正在检查谁是类最高的人一样，并且通过这些选项之一(1,3)再次说明他是并且没有理由检查所有类(class)。

我确实知道，如果我们要检查最坏的情况，那么这些陈述都不会是真的，因为没有任何假设或额外内存的最佳排序算法是 Omega(nlogn)。

重要说明:我不是在寻找解决方案(一种能够进行匹配排序的算法)- 只是想更好地理解这个概念。

谢谢!

Answer 1

对于 1+3 问问自己 - 您是否知道一种算法可以在 Theta(n) 中对数组进行最佳排序 - 如果答案为真，则1+3 都是真的——因为 Theta(n) 是 O(n) [intersection] Omega(n)，因此如果你有这样的算法(最好在 Theta(n) 中运行case) - 1+3 都是正确的。
提示:优化bubble sort .

对于 2:问问自己 - 是否每个算法都在 O(n) 最佳情况下对数字数组进行排序？您知 Prop 有最坏情况和最佳情况相同时间复杂度的算法吗？如果取消所有优化，上述冒泡排序会发生什么情况？

对于 4:问问自己 - 您是否需要读取所有元素以确保数组已排序？如果你这样做 - Omega(n) 是一个明确的下限，你不能比它更好。

祝你好运!