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

Question

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

Answer 1

从等式是有点向后思维的它开始。你真正关心的是可扩展性，或者，有什么事要你增加输入的大小做。

如果你只是有一个循环，例如，你有一个O（n）的时间复杂度算法。如果您有其他循环内的循环，虽然，它变成为O（n ^ 2），因为它现在必须为任何规模大小n个输入做N ^ 2很多东西。

当你谈论最坏的情况下，你通常所说的非确定性算法，在那里你可能有一个环，可提前停止。你想为这个做的是最坏的假设，假装循环将尽可能晚地停止。因此，如果我们有：

  

有（INT I = 0; I 0.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 就容易多了。