performance - 例如在这个插入排序算法中，我如何证明算法的时间复杂度是 O(n^2)？

Question

采用以下插入排序算法:

通过检查我知道它的 O(n^2) 相当容易。但就证明而言，它是 O(n^2)，我该怎么做呢？我可以将所有操作相加，但据我所知，n + "sum of j=2 to n" 不会真正导致 n^2。

我真的不知道如何准确地证明这一点。有人可以尝试清楚地解释我将如何以对 O(n^3) 算法也适用的方式来证明这一点吗？

Answer 1

您可以通过考虑在最坏情况 中执行多少操作来证明大 O 复杂性。您已经完成了计数部分并将结果输入到图像的右侧栏中，因此还有待证明的是主导项是 O(n^2)。

除了涉及总和的项外，您的程序包含执行 n-1 次的指令，因此这些都是 O(n) 项。

现在是总和的条款。在最坏的情况下，t_j 可以是 j，因为您最终可能会递减 i，您将其设置为 j 所有下降到 0 的方式。所以在这种最坏的情况下，我们有 t_j = j 然后你有一个 sum from 2 to n of j 是 O(n^2)。这是由于遵循数学恒等式:

这可以通过将这些系列中的两个加在一起来证明，注意将总和为 n+1 的两个项加在一起，然后将总和除以二。看看 proof in wolfram .

最后，由于 O((n^2 + n)/2) = O(n^2) 你会发现包含总和的项在运行时占主导地位，这就是算法的原因是 O(n^2)