algorithm - 壳排序分析

Question

我正在阅读一本关于算法的书，其中提到了关于 shell 排序算法的分析，如下所示：

Shellsort 的最坏情况运行时间，使用 Shell 的增量，是 Theta(n square)。

证明不仅需要显示最坏情况运行时间的上限，而且还需要显示存在一些输入实际上将下限作为 Omeaga(n 平方) 时间运行。我们首先通过构造一个坏案例来证明下界。

我上面的问题是：

1. 为什么作者提到坏情况来检查下限？我教要获得下限，我们应该采取最好的情况，请在上面澄清。

谢谢！

Answer 1

要显示某事是Theta(f(n))，必须同时显示上限和下限，这就是文本正在执行的操作。

“最坏情况时间是 Theta(n square)”的说法要求人们同时证明所述最坏情况时间的上限和下限。

类似地，关于平均案例时间为 Theta(f(n)) 的陈述将需要平均案例时间的两个界限。

等等。

正如@Patrick87 简洁地说：

边界与情况正交。

Answer 2

他同时考虑上限和下限的原因是因为他想使用Theta(Θ) 表示法来表达最坏情况下的时间。

theta 表示法要求您同时建立上限和下限。

Answer 3

Theta 是一个边界约束（上限和下限）。要显示算法具有运行时间 Theta(f(n))，您必须确定两件事：

1) 在最坏的情况下，算法在所有情况下运行时间为 O(f(n)) [最坏情况复杂度]

2) 算法必须花费时间 Omega(f(n)) [有真实的例子可以达到最坏的情况]

您通过为算法找到特别糟糕的情况来建立第二部分。