algorithm - 确定算法的最坏情况复杂度

Question

有人可以向我解释如何确定算法的最坏情况复杂性。我知道我们需要使用方程 W(n) = max{t(I)|I 的 D 元素)，其中 D 是大小为 n 的输入集。我是否计算为每个元​​素执行的操作次数，然后取其最大值？有什么更简单的方法可以做到这一点？

Answer 1

从方程式开始考虑有点倒退。你真正关心的是可扩展性，或者，当你增加输入的大小时它会做什么。

例如，如果您只有一个循环，那么您就有一个 O(n) 时间复杂度算法。但是，如果您在另一个循环中有一个循环，则它变为 O(n^2)，因为它现在必须为任何大小的 n 输入执行 n^2 很多事情。

当您谈论最坏的情况时，您通常谈论的是非确定性算法，其中您可能有一个可以过早停止的循环。为此，您要做的是假设最坏的情况并假装循环将尽可能晚地停止。所以如果我们有：

for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(rand() > .5) j = n; } }

我们会说最坏的情况是 O(n^2)。尽管我们知道中间循环很可能会提前结束，但我们正在寻找可能的最差性能。

Answer 2

这个方程更像是一个定义而不是一个算法。

所讨论的算法是否关心输入大小以外的任何内容？如果不是，那么计算 W(n) 是“容易的”。

如果是这样，请尝试提出病态输入。例如，使用快速排序，很明显排序后的输入是病态的，您可以进行一些计数以查看它需要 O(n^2) 步。那时你可以

1. 认为您的输入“最大程度”是病态的
2. 在任何输入的运行时显示匹配的上限

#1 的示例：

每次快速排序都会将枢轴放在正确的位置，然后在这两个部分上递归。（手电警报）最坏的情况是让阵列的其余部分位于枢轴的一侧。排序的输入实现了这一点。

#2 的例子：

快速排序的每一遍都将枢轴放在正确的位置，因此不会超过 O(n) 遍。每次通过不超过 O(n) 的工作。因此，没有任何输入会导致快速排序的时间超过 O(n^2)。

在这种情况下，＃2要容易得多。