如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
能否通过计算机找到适合速拧的魔方解法？工程上存在那么多不确定情况，为什么计算机不能利用它们产生真随机数，而只能根据逻辑产生伪随机数？
学了四年算法，码了五万行代码，但是大一期末C语言模拟及不了格怎么办？
有哪些解决完之后让你拍案叫绝的算法问题？
比特币的算法到底在算什么？
如何看待滴滴章文嵩称，滴滴面临的问题比 AlphaGo 复杂 100 倍？
你在生活中用过最高级的算法知识是什么？
可以利用抄代码来同时记忆算法与练英文书法吗？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
如何利用群论的知识解决三阶魔方？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
我们高中数学为什么不重视算法？高中学的数列，三角函数，求导，圆锥曲线相关问题的解法和算法有什么关系？如何通俗易懂地解释遗传算法？有什么例子？
感觉算法在程序员中快被吹上天了，如果只是搞编程的话，是不是没必要死磕算法？
谷歌翻译这几个月的进化速度突然加快是什么原因？
为什么算法时间复杂度没有三角函数级别？
如何看待 2021 年图灵奖授予美国计算机科学家 Jack J. Dongarra?
作为学数学的人，你有哪些用于「双十一」购物的方法？
为什么很多程序无法计算负数的立方根？
为什么现在有这么多人工智能无用论？
如何把梯度传递过Argmax?
智能座舱的算法包括哪些方面？
将并行计算纳入算法竞赛，是否合适？
如何直观地解释 backpropagation 算法？
你见过哪些神一样的优化操作？
为什么在数学中，一些运算的逆运算比原运算难很多？
为什么根据数组下标获取数据时间是一样的，难道下标不用寻址吗？
戴克斯特拉算法（Dijkstra）的本质是贪心，还是动态规划？
如何直观地解释 backpropagation 算法？
如何评价姜新文老师提出的NP=P这篇文章？
备战ACM，想问下有什么算法网课推荐吗?
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
Minecraft 的地形生成算法是什么？
使用数组可以表示哪些数据结构？
Auto X的自动驾驶技术用了什么技术？
算法A时间复杂度O(n²)，算法B时间复杂度为O(n³)，为什么选择算法B而不选算法A的6个理由?
为什么说程序员要贷款买房之前最好先学好数据结构和算法？
100个金币，只有1个略重，其余99个一样重。给你一个天平，最少称几次能确保找出那个略重的?
递归和循环相比耗费更多的空间，对于循环来说除了可以简化逻辑外还有什么优点吗？
《阮一峰版快速排序完全是错的》一文是否存在事实错误？
天天P图中我的小学生证件照功能怎么实现的？算法是什么样？