如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
想在业余时间刷leetcode，配合什么书籍/课程/视频网站一起刷leetcode的效率最高？cpp是不是最方便研究算法的语言？
比特币的算法到底在算什么？
计算机开发岗和算法岗都有些什么区别？
圆桌上 1000 个人轮流开枪，最后活下来的是几号？
Auto X的自动驾驶技术用了什么技术？
到了 2022 年，人工智能有哪些真正可落地的应用？
如何正确地用 Test Driven Development 实现算法？
利用无理数压缩数据是否可行？
正负样本极不平衡的问题？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
链表求交集，从链表头删去一长串而非一个节点？（已解决）?哪些看似与图论无关的问题可用图论模型解决？
为什么说程序员要贷款买房之前最好先学好数据结构和算法？
N个互异数随机组成的数组的逆序数的分布公式是什么？
请问有哪些最优化算法可以做全局优化？
「贪心算法」的算法思路是什么，它存在什么缺陷？
有哪些数学定理或者数学知识惊呆了你？
世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？
有哪些手算对数的方法？
PRML为何是机器学习的经典书籍中的经典？
如果想大体地了解凸优化和非凸优化中比较重要的概念、理论知识和算法应该看哪些书籍或者论文？
如何直观地解释 backpropagation 算法？
如何直接跳出深层递归而不是一层一层跳出？
哪本《数据结构与算法》最好？
如何通俗易懂地解释遗传算法？有什么例子？
使用数组可以表示哪些数据结构？
开发一个 App，利用 Bose 降噪耳机的原理实现其功能？
一个关于拓扑排序的扩展问题，可以做到的最优复杂度是？
想学好计算机算法，是否需要重新学数学呢?
如何找到一个10项的非负整数数列，使该数列的任意不超过3项的和不重复，并使数列的最大项最小，并证明?
请教拓扑排序中的一点疑问？
如何对一个元素只有0和1的数组进行排序？
备战ACM，想问下有什么算法网课推荐吗?
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
算法老师劝学生放弃学习 JavaScript，我该怎么办？
MIT 猎豹机器人算法有多复杂？中国是否能研发出这种机器人？
如何面对算法竞赛的焦虑？
如何证明快速排序法的平均复杂度为 O(nlogn)？
ICLR 2019 有什么值得关注的亮点？
你靠哪些讲解学会了曾经怎么也学不会的算法？