1

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

我试图了解以下陈述之间的区别：

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

我将首先解释是什么让我发疯。我不确定 1 和 3 - 但我知道其中一个的答案是正确的，只需指定一种情况，而另一种情况的答案是通过检查所有可能的输入是正确的。因此，我知道其中一个必须是正确的，只需指定数组已经排序，但我不知道是哪个。我的老师总是告诉我要像我们正在检查谁是班上最高的人一样思考它，并且再次通过这些选项之一（1,3）就足以说他是并且没有理由检查所有班级。

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

重要提示：我不是在寻找解决方案（一种能够进行匹配排序的算法）——只是试图更好地理解这个概念。

谢谢！

4

2 回答 2

2

对于 1+3问问自己 - 你知道一个算法可以在最好的情况下对数组进行排序Theta(n)- 如果答案是真的，那么两个 1+3 都是真的 - 因为 Theta(n) 是O(n) [intersection] Omega(n)，因此如果你有这样的一种算法（在 Theta(n) 最佳情况下运行）- 1+3 都是正确的。
提示：优化冒泡排序。

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

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

祝你好运！

于 2013-02-03T09:50:10.873 回答
1

显然，区别在于“O”和“Omega”。一说“上升不快于”，二说“上升不慢于”。

确保您了解这些术语之间的区别，并且您会看到句子中的区别。

1 和 3 都表示完全不同的事物，就像 2 和 4 一样。

看看那些（那些不一样！）：

1~有一个算法，10个项目在最好的情况下不会超过30个。
3~ 存在一个算法，10 个项目在最好的情况下不会少于 30 个。

2~ 10个项目的每个算法在最好的情况下不超过30个。
4~ 10个项目的每个算法最好情况下不少于30个。

你现在感觉到不同了吗？O/Omega 的区别是相似的，但研究的主题不同。上面的例子说明了在某些点/情况下的不同性能，而 O/Omega 表示法告诉你性能，与数据的大小有关，但前提是数据“足够大”，无论是三个项目还是百万个，以及它会降低常数因子：

function 1000000*n is O(n)
function 0.00000*n*n is O(n^2)

对于少量数据，第二个显然比第一个好得多。但是随着数据量的增加，很快第一个开始变得更好！

将上述示例重写为“更合适”的术语，与您的原始句子更相似：

1~ 存在一种算法，对于 N 个以上的项目，在最好的情况下不超过 X*N。
3~ 存在一种算法，对于 N 个以上的项目，在最好的情况下不会少于 X*n。

2~ 每个算法，对于超过 N 个项目，在最好的情况下不超过 X*N。
4~ 每一个算法，对于多于 N 个项目，在最好的情况下不小于 X*N。

我希望这可以帮助您“看到”/“感受”差异！

于 2013-02-03T10:49:33.587 回答