难道在快速排序的数据透视表值的某些值是对数的情况下？
不。
无论您选择哪个枢轴值，第一个分区都将花费O(n)时间-您需要将每个其他元素与枢轴进行比较。
O(n)
此后，您递归并对两个分区执行相同操作-枢轴的最佳选择（当每个枢轴是范围的中间值时）最终的复杂度为O(n log n)。枢轴的最差选择（当每个枢轴是范围内的最大值或最小值时）最终的复杂度为O(n^2)。
O(n log n)
O(n^2)
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
点击生成二维码
我来说两句