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

Question

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

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 就容易多了。