如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
可以利用抄代码来同时记忆算法与练英文书法吗？你写过哪些比较酷的十行以内的 Matlab 代码？
如何通俗地讲解 viterbi 算法？
如何理解算法时间复杂度的表示法，例如 O(n²)、O(n)、O(1)、O(nlogn) 等？
如何系统学习机器学习？
如果一个算法空间复杂度是指数级，时间复杂度是多项式级，那么这个算法复杂度怎么算呢？
目标检测算法中Two-stage算法速度慢,到底在哪里?
算法岗位真的需要顶会才能入场吗？
谷歌翻译这几个月的进化速度突然加快是什么原因？
EM算法存在的意义是什么？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
Cambridge Analytica 是一家怎样的公司？如何理解计算物理中的元胞链接列表（Cell Linked List）算法？
未来会不会有一种方式，可以使一部蓝光电影压缩到几Mb甚至几Kb？
如何分配砝码使天平尽可能平衡？
c++怎么在1到n这些数中随机产生k（k<n）个？当然，k个数互不相等。有什么比较好的写法吗？
有哪些手算对数的方法？
有没有手算根号pi的方法？
报了蓝桥杯比赛，几乎零基础，如何准备，请大牛指导一下。谢谢？
如何编程判断一个数是否是质数？
Algorithmic Game Theory 和经济学中的 Game Theory 相似度大吗？
为什么同样是解决一个问题，别人就能想出算法，而我却绞尽脑汁，百般尝试也不得其法？
有没有可能让计算机去理解代码，从而写代码？
哪位大佬能来个骨灰级的红黑树讲解啊？
100个金币，只有1个略重，其余99个一样重。给你一个天平，最少称几次能确保找出那个略重的?
如何对一个元素只有0和1的数组进行排序？
面试题:一个长度为n的数组，其中数组中每个元素的值都不大于n，如何用O(n)的算法判断数组中是否存在重复元素?
为什么根据数组下标获取数据时间是一样的，难道下标不用寻址吗？
可以利用抄代码来同时记忆算法与练英文书法吗？
网上常能见到的一段 JS 随机数生成算法如下，为什么用 9301, 49297, 233280 这三个数字做基数？
如何统计拓扑排序的个数？
在校生为了面试，有必要强行记住一些复杂算法如红黑树、KMP等的实现吗？
这张算数入门图（一只兔子加一只兔子）里的题在算什么？
是否存在时间复杂度是O(tan N)的算法？
有没有手算根号pi的方法？
如何判断这两份代码的时间复杂度？
MIT 猎豹机器人算法有多复杂？中国是否能研发出这种机器人？
TikTok、抖音为什会成功，以至于微信、Google、Facebook 等大厂在短视频领域都折戟？
如何把梯度传递过Argmax?
数据结构与算法在工作的作用及其大学学到什么程度才算可以?
数字图像处理的工作是用传统算法更多还是用深度学习更多?