如何理解快速排序的时间复杂度是O(nlogn)
排序 如何 快速 时间 理解 复杂度
2023-09-11 14:19:00 时间
本文转载自:https://blog.csdn.net/u011947630/article/details/104691611
选择排序、冒泡排序等算法的时间复杂度都比较好理解,但不是很清楚快速排序的时间复杂度为什么是O(nlogn)。从《算法图解》中看到的思路,很赞,解决了一直以来的疑惑。
引用自《算法图解》:
快速排序的情况比较棘手,在最糟情况下,其运行时间为O(n2)。。在平均情况下,快速排序的运行时间为O(nlogn)。
平均情况与最糟情况
快速排序的性能高度依赖于你选择的基准值。
- 最糟情况
假设你总是将第一个元素用作基准值,且要处理的数组是有序的。由于快速排序算法不检查输入数组是否有序,因此它依然尝试对其进行排序。注意,数组并没有被分成两半,相反,其中一个子数组始终为空,这导致调用栈非常长。 - 平均情况
假设你总是将中间的元素用作基准值,在这种情况下,调用栈如下。 调用栈短得多!因为你每次都将数组分成两半,所以不需要那么多递归调用。你很快就到达 了基线条件,因此调用栈短得多。
第一个示例展示的是最糟情况,而第二个示例展示的是最佳情况。在最糟情况下,栈长为 O(n),而在最佳情况下,栈长为O(log n)。
现在来看看栈的第一层。你将一个元素用作基准值,并将其他的元素划分到两个子数组中。 这涉及数组中的全部8个元素,因此该操作的时间为O(n)。在调用栈的第一层,涉及全部8个元素, 但实际上,在调用栈的每层都涉及O(n)个元素。
即便以不同的方式划分数组,每次也将涉及O(n)个元素。
在这个示例中,调用栈的高度为O(log n),而每层需要的时间为O(n)。因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。这就是最佳情况。 在最糟情况下,有O(n)层,因此该算法的运行时间为O(n) * O(n) = O(n2)。
相关文章
- TreeMap和TreeSet在排序时如何比较元素?
- linux Command sort 排序
- C++程序设计:原理与实践(进阶篇)16.8 排序和搜索
- 快速排序及优化
- v8引擎如何实现sort排序的?
- 快速排序、冒泡排序、数组全排列
- linux如何排序去重
- python学习之利用format()或zfill()函数对数据进行编号排序的应用
- Mysql Order By 字符串排序,mysql 字符串order by
- MySQL也有潜规则 – Select 语句不加 Order By 如何排序?
- dart - 如何制作新数组嵌套排序映射
- Ch8. 排序
- 排序算法--简单选择排序
- ASPxGridView 排序、分页、加载数据必需的三个函数
- [LeetCode] Max Chunks To Make Sorted 可排序的最大块数
- leetcode 451. Sort Characters By Frequency 根据字符出现频率排序