上限、下限

Question

证明算法的上限或下限意味着什么？

Answer 1

证明上限意味着您已经证明该算法将使用不超过对资源的某些限制。

证明下限意味着您已经证明该算法将使用不小于对资源的某些限制。

＆QUOT;资源＆QUOT;在这种情况下，可能是时间，内存，带宽等。

Answer 2

上限和下限与算法的最小和最大“复杂性”有关（我谨慎地使用这个词，因为它在复杂性分析中具有非常具体的含义）。

以我们的老朋友冒泡排序为例。在所有数据都已排序的理想情况下，所花费的时间为 f(n)，该函数取决于 n, ，列表中的项目数。这是因为您只需对数据集进行一次传递（零交换）即可确保列表已排序。

在特别糟糕的情况下，数据按照与您想要的顺序相反的顺序排序，所花费的时间变为 f(n²）。这是因为每一遍都会将一个元素移动到正确的位置，并且您需要 n 通过执行所有元素。

在这种情况下，即使 big-O 复杂度保持不变，上限和下限也不同。

顺便说一句，冒泡排序备受诟病（通常有充分的理由），但在某些情况下它是有意义的。实际上，我在一个应用程序中使用它，其中大部分数据已经排序，并且一次只会将一两个项目添加到列表末尾。对于添加一项，并使用反向冒泡排序，您可以保证新列表将一次性排序。这说明了下界概念。

事实上，您可以对冒泡排序进行优化，将下界设置为 f(1)，只需提供指示列表是否已排序的额外数据即可。您可以在排序后设置此项，并在将项目添加到末尾时清除它。

Answer 3

无论边界（上限或下限）如何，我们总是在谈论我们可以考虑的最坏情况输入。例如，在排序中，我们假设最坏情况是未排序的输入列表。

我的理解是问题有一个下限。例如，我们说基于比较的排序的下限是\ Omega（n log n）;我们没有假设我们使用什么特定的基于比较的排序算法。无论算法（合并排序，快速排序等），我们都不能比\ Omega（n log n）的这个边界做得更好。下划线直观地告诉我们，特定的问题有多难。

当我们谈论一个特定的算法时，我们谈论上限。例如，我们说冒泡排序的上限是O（n ^ 2），合并排序的上限是O（n log n）。直观地说，上限告诉我们一个特定的算法在解决问题方面有多好。