algorithm - 算法分析(复杂度)

Question

如何分析算法？是什么让快速排序具有 O(n^2) 的最坏情况性能，而合并排序具有 O(n log(n)) 的最坏情况性能？

Answer 1

这是整个学期的主题。最终，我们讨论的是在算法完成之前必须完成的操作数量的上限，作为输入大小的函数。我们不包括系数(即 10N 与 4N^2)，因为对于足够大的 N，它不再重要。

如何证明算法的大 O 是什么可能非常困难。它需要一个正式的证明，并且有很多技术。通常一个好的临时方法是只计算算法对数据的传递次数。例如，如果您的算法有嵌套的 for 循环，那么对于 N 项中的每一项，您都必须运行 N 次。这通常是 O(N^2)。

至于合并排序，您将数据一遍又一遍地分成两半。这需要 log2(n)。对于每个拆分，您都会传递数据，这会给出 N log(n)。

快速排序有点棘手，因为在平均情况下它也是 n log (n)。您必须想象如果您的分区拆分数据时会发生什么情况，这样每次您只在分区的一侧获得一个元素。然后你需要将数据拆分 n 次而不是 log(n) 次，这使得它成为 N^2。快速排序的优点是它可以原地完成，而且我们通常可以获得更接近 N log(n) 的性能。