可以这样来看双路快速排序的算法复杂度吗
来源：2-4 快速排序算法的复杂度分析
Wonwayshon
2021-04-12 22:35:34
我的想法主要是看对于大量任意的输入数据情况下排除特殊输入分析能够想到的最好和最坏情况，具体想法如下
对于大量任意的输入数据来说，双路快速排序最坏的情况应该就是恶化时成为o(n²)级别，那么如果每一次都是正好从中间分成两部分应该是最理想的情况？这个时候算法是o(nlogn)级别，可以理解成对于大量任意的输入数据情况下双路快速排序算法的复杂度在o(nlogn)级别到o(n²)级别之间波动吗？同样的对于归并排序对于大量任意的输入数据情况算法的复杂度保持o(nlogn)级别。
写回答
1回答
-
课程中实现的快速排序算法，最坏复杂度就是 O(n^2)，即每次标定点都非常“不幸”的选在了待处理区间的最大值或者最小值。
但是，课程中介绍了，这个概率太低了。所以此时，这个最坏复杂度是不实用的。因为你不能稳定地找到一组数据，让这个算法稳定地是 O(n^2) 级别的，虽然理论上存在这个可能。而实际上，99.999999999999999999999999999% （可能还要更多地 9）的概率，他是 O(nlogn) 的。
此时，我们在处理一个随机算法。对于随机算法来说，我们应该分析它的期望。快速排序算法的期望是 O(nlogn) 的。
继续加油！：）
0h021-04-13
相似问题