上限,下限

Question

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

Answer 1

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

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

此上下文中的"资源"可以是时间,内存,带宽或其他内容.

Answer 2

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

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

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

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

顺便说一句，气泡排序是非常有害的（通常是出于充分的理由），但是在某些情况下它是有道理的。我实际上是在应用程序中使用它的，在该应用程序中已经对大部分数据进行了排序，并且往往一次只将一两项添加到列表的末尾。对于添加一项，并使用反向气泡排序，您可以保证新列表将一次性通过。这说明了下界概念。

实际上，您可以通过提供一个额外的数据来指示列表是否已排序，来对冒泡排序进行优化，从而将下界设置为f（1）。您可以在排序后进行设置，并在最后添加项目时将其清除。