算法分析（复杂度）

Question

如何分析算法？是什么让快速排序有O(n^2)最糟糕的表现，而合并排序有O(n log(n))最差的表现？

Answer 1

这是整个学期的话题。最终，我们正在讨论算法完成之前必须完成的操作次数的上限，作为输入大小的函数。我们不包括coeffecients（即10N vs 4N^2），因为对于N足够大，它已经不重要了。

如何证明一个算法的大噢可能是相当困难的。它需要一个正式的证据，并有许多技术。通常，一种很好的特殊方法是只计算算法产生的数据通过次数。例如，如果您的算法嵌套for循环，则对于N个项目中的每一个，您必须操作N次。那通常是O（N^2）。

至于合并排序，你一次又一次地分割数据。这需要log2（n）。并且对于每个分组，您对数据进行传递，这会得到N log（n）。

快速排序有点棘手，因为在平均情况下它也是n log（n）。你必须想象如果你的分区分裂了数据，那么每当你在分区的一侧只有一个元素时会发生什么。那么你将需要分割数据n次而不是log（n）次，这使得N^2。快速排序的优势在于它可以在适当的位置完成，而且我们通常可以接近N log（n）性能。

Answer 2

quicksort和merge sort将数组分成两部分，递归地对每个部分进行排序，然后合并结果。 Quicksort通过选择“pivot”元素进行分割，并将数组分割为更小或更大的数据，然后将数据分割为数据透视。合并排序可以任意分割，然后以线性时间合并结果。在这两种情况下，单个步骤是O（n），并且如果每次数组大小减半，则这会给出对数数量的步骤。所以我们期望O（n log（n））。

然而，快速排序有一个最坏的情况，即分裂总是不均匀的，所以你没有得到与n的对数成比例的许多步骤，而是与n成正比的许多步骤。合并排序完全分为两部分（或尽可能接近），所以它没有这个问题。

Answer 3

• 快速排序有许多变种取决于枢选择
• 假设我们总是在数组中选择第一个项目为支点

如果输入数组进行排序，然后快速排序将只有一个种类选择排序！ 因为你并不是真的把数组分开..你只是在每个周期中挑选第一个项目

另一方面，合并排序总是会以相同的方式分割输入数组，无论其内容如何！

另请注意：分割和征服时分割长度相等时的最佳性能！

Answer 4

1. 这是算法课程资料的入门分析。

2. 操作被定义（即乘法），并且分析是按空间或时间进行的。

3. 此操作按空间或时间计算。通常，分析按照输入大小时间作为因变量执行。

实施例的伪代码：

foreach $elem in @list 

    op(); 

endfor 

会有Ñ操作来执行，其中Ñ是@list大小。如果你不相信我，请自己计算一下。

要分析quicksort和mergesort需要一个体面的水平的所谓的数学成熟。松散地，你可以求解一个由递归关系导出的离散微分方程。