如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
李彦宏批评推荐式算法，你怎么看？经过足够长的时间， AlphaGo 的棋谱能收敛到一张上吗？
对于编程思想和能力有重大提升的书有哪些?
如何证明快速排序法的平均复杂度为 O(nlogn)？
如何面对算法竞赛的焦虑？
是否存在一个函数，使得它的逆运算是容易求的，而它的逆运算的逆运算是难求的？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
如何理解算法时间复杂度的表示法，例如 O(n²)、O(n)、O(1)、O(nlogn) 等？
有哪些解决完之后让你拍案叫绝的算法问题？
100个金币，只有1个略重，其余99个一样重。给你一个天平，最少称几次能确保找出那个略重的?
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
美剧《硅谷》第三季第一集神秘代码写的是什么？一道程序员面试题？
如何评价Google 在TensorFlow 中引入的bfloat16 数据类型？
什么是机器学习？
面试题:一个长度为n的数组，其中数组中每个元素的值都不大于n，如何用O(n)的算法判断数组中是否存在重复元素?
为什么算法时间复杂度没有三角函数级别？
报了蓝桥杯比赛，几乎零基础，如何准备，请大牛指导一下。谢谢？
如何证明快速排序法的平均复杂度为 O(nlogn)？
哪段代码最能代表程序员的暴力美学？
如何学习视频识别技术？
如何评价姜新文老师提出的NP=P这篇文章？
有什么理论复杂但是实现简单的算法？
程序员能 20 分钟徒手写出一个没 bug 的 KMP 算法吗？（可以调试）
蒙特卡罗算法是什么？
是否存在一个字符串，它的md5值是其自身？
在一段高速公路上，30分钟之内见到汽车经过的概率是95%，那么，在10分钟内见到汽车经过的概率是多少？
参加 ACM-ICPC World Final 是怎样一种体验？
有没有能向玩家保证服务器发牌时没有作弊的牌类游戏发牌算法？
只需4组数据，还原你的购物模式，具体算法是怎么实现的？
Apriori算法是什么？适用于什么情境？
计算机视觉（CV）的算法有哪些，具体都有哪些特点？
如何系统地学习算法？
如果按国家分，哪个国家编程最厉害？有没有代表人物？
二分查找有几种写法？它们的区别是什么？
利用无理数压缩数据是否可行？
构建进化树的意义是什么？除了看亲缘关系之外。
如何用一个1-8随机数生成器制作一个1-7随机数生成器？
如果按国家分，哪个国家编程最厉害？有没有代表人物？
有哪些算法惊艳到了你？
只需4组数据，还原你的购物模式，具体算法是怎么实现的？