算法是如何被分析的？为什么快速排序具有 O(n^2) 的最坏情况性能，而归并排序具有 O(n log(n)) 的最坏情况性能？
算法分析（复杂度）
5
- Yktula
5个回答
6
那是一个需要整学期来讲的话题。最终，我们所说的是算法完成前必须完成的操作数量的上限与输入大小的函数关系。我们不包括系数（例如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)的性能。
如何证明算法的大O复杂度可能相当困难。它需要正式的证明，并且有许多技巧。通常一种好的临时方法是计算算法对数据进行了多少次传递。例如，如果您的算法具有嵌套的for循环，则每个N项必须操作N次。那通常会是O(N^2)。
至于归并排序，您将数据一分为二，然后一遍又一遍地重复此过程。这需要log2(n)步骤。并且对于每个划分，您都需要在数据上进行一次传递，这会得到N log(n)。
快速排序有点棘手，因为在平均情况下，它也是n log (n)。您必须想象一下，如果您的分区将数据分成只有一个元素的情况，那么您需要将数据分割n次而不是log(n)次，这将使其成为N^2。快速排序的优点是可以原地完成，并且通常可以获得更接近N log(n)的性能。
- frankc
1
这是算法课程的入门分析材料。
定义了一个操作（例如乘法），并以空间或时间为单位进行分析。
该操作按照空间或时间计数。通常，分析是以时间作为输入大小的依赖变量进行的。
示例伪代码：
foreach $elem in @list
op();
endfor
将执行n次操作，其中n是@list的大小。如果您不相信，请自己数一下。
要分析快速排序和归并排序需要相当程度的数学素养。粗略地说，您需要解一个从递归关系导出的离散微分方程。
- Paul Nathan
1
如何计算操作的加法非常重要。我已经提高了这个“答案”的分数。 - mozillanerd
0
- 快速排序有许多变体，取决于枢轴的选择
- 假设我们总是选择数组中的第一个项目作为枢轴
如果输入数组已排序，则快速排序将仅成为一种选择排序！因为您实际上并没有真正地分割数组...您只是在每个循环中选择第一个项目
另一方面，无论其内容如何，归并排序始终会以相同的方式划分输入数组！
还要注意：在分治法中，当分割长度-几乎-相等时，性能最佳！
- Betamoo
0
分析算法是一项艰苦且容易出错的工作。我会将其比作一个问题，比如在桥牌游戏中，我有多少机会同时得到两张A牌。必须仔细考虑所有可能性，并且不能忽略A牌可能以任何顺序到达。
因此，为了分析这些算法，我们需要通过实际伪代码来查看算法并确定最坏情况下的结果。以下是粗略概述：
对于快速排序，我们需要选择一个枢轴来分割集合。如果非常不幸，集合每次都会被分成一个n-1的子集和一个1的子集，需要进行n个步骤，每个步骤都要检查n个元素。这会导致N^2次操作。
对于归并排序，我们首先需要将序列分成按顺序排列的子序列。即使在最坏的情况下，最多也只有n个子序列。可以将这些子序列两两组合，之后再将更大的集合两两组合等等。但是，在最初的（最多）n/2个组合中，处理的是极小的子集；而在最后一步处理的子集大小约为n，但只有一步。这会导致N.log(N)次操作。
因此，为了分析这些算法，我们需要通过实际伪代码来查看算法并确定最坏情况下的结果。以下是粗略概述：
对于快速排序，我们需要选择一个枢轴来分割集合。如果非常不幸，集合每次都会被分成一个n-1的子集和一个1的子集，需要进行n个步骤，每个步骤都要检查n个元素。这会导致N^2次操作。
对于归并排序，我们首先需要将序列分成按顺序排列的子序列。即使在最坏的情况下，最多也只有n个子序列。可以将这些子序列两两组合，之后再将更大的集合两两组合等等。但是，在最初的（最多）n/2个组合中，处理的是极小的子集；而在最后一步处理的子集大小约为n，但只有一步。这会导致N.log(N)次操作。
- Albert van der Horst
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接