~技术问答题~
返 回

No.791 快排原理以及时间复杂度,为什么(淘系前端)

题目描述~ 略...

寄语:问题比答案更重要

建议自己先有个思考的过程,有了自己的答案或者疑问再看解析进行对比。

目前解析在逐步添加中,也可以跳转链接查看。

「解析1

快排和归排的复杂度都是O(n*log n),为什么都用快排而不用归排?

看了《算法图解》之后,大致理解了是什么原因,真正的原因是:不可描述的常量导致使用快排而不是归排。

好了,真正的解释是这样的:

算法的每一步实际上都需要一个固定时间量,被称为常量。我们平时考虑时间复杂度的时候并不考虑常量的影响,但有时候常量的影响不可忽略,比如在这个问题上。但是大多数时候考虑复杂度的时候,可能还是不需要考虑常量的影响的,嗯,我觉得是……由于算法的每一步都有一个常量,而快排的常量比归排小,因此虽然两者的复杂度相同,但是快排更快一些。

那第二个问题就来了,归排的复杂度一直都是O(nlog n),而快排的平均复杂度才是O(nlog n),最坏情况下快排的复杂度可以达到O(n^2),为什不怕快排的时候是最坏的情况呢?主要是因为绝大多数情况下,快排遇到的都是平均情况,也就是最佳情况,只有极个别的时候会是最坏情况,因此往往不考虑这种糟糕的情况。


作者:吉大秦少游 原文链接:https://blog.csdn.net/zhanshen112/article/details/85211505

其他参考:https://blog.csdn.net/qq_20746945/article/details/89378662

解析或答案仅供参考。

关于作者

zz_jesse 专注前端

掘金 我的开源项目

公众号@前端技术江湖

一个可以帮开发者成长的公众号前端面试题库更新通知前端学习资料、干货文章

技术交流群

交流中成长大厂内推机会