algorithm - 上限，下限

Question

证明算法的上限或下限是什么意思？

Answer 1

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

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

在这种情况下，“资源”可以是时间、内存、带宽或其他东西。

Answer 2

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

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

在数据以与您想要的顺序相反的顺序排序的特别糟糕的情况下，所花费的时间变为 f(n ² )。这是因为每次传递都会将一个元素移动到正确的位置，并且您需要n传递来完成所有元素。

在这种情况下，上限和下限是不同的，即使大 O 复杂度保持不变。

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

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

Answer 3

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

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

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