如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
你在生活中用过最高级的算法知识是什么？Matlab中的conv函数与卷积公式是什么关系呢？
如何对一个元素只有0和1的数组进行排序？
想在业余时间刷leetcode，配合什么书籍/课程/视频网站一起刷leetcode的效率最高？
如何通俗的解释模糊神经网络？
为什么时效上具有明显优势的基数排序（radix sort）没有快速排序流行？
能否使用神经网络来判断奇偶数？
如何理解计算物理中的元胞链接列表（Cell Linked List）算法？
在知乎你见过哪些明显抱团点反对的问题，对社区有怎样的影响，你有什么好的建议？
如何看待淘宝、微信、抖音推出算法关闭键？会带来哪些影响？还有哪些问题值得关注？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
机器学习的算法和普通《算法导论》里的算法有什么本质上的异同？如何用一个1-8随机数生成器制作一个1-7随机数生成器？
开发一个 App，利用 Bose 降噪耳机的原理实现其功能？
将并行计算纳入算法竞赛，是否合适？
有没有可能让计算机去理解代码，从而写代码？
如何看待2021年秋招算法岗灰飞烟灭？
电子设备（如电脑）内置时钟的算法是如何“分辨/度量”出一秒的长度的？
谷歌翻译这几个月的进化速度突然加快是什么原因？
掷一枚不均匀的硬币，正面概率为0.7，反面的概率为0.3，如何最高效地获得一个概率为0.5的事件？
这张算数入门图（一只兔子加一只兔子）里的题在算什么？
备战ACM，想问下有什么算法网课推荐吗?
uber优惠码的生成的规则是什么？
什么是 hash？
如何判断这两份代码的时间复杂度？
算法研究属于数学专业还是计算机专业？
是否存在时间复杂度是O(tan N)的算法？
沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌 ）是怎样的？
如何看待淘宝、微信、抖音推出算法关闭键？会带来哪些影响？还有哪些问题值得关注？
如果有人想走遍中国所有的省级行政区（含港澳台），总路程最小可以是多长？
如何证明快速排序法的平均复杂度为 O(nlogn)？
未来会不会有一种方式，可以使一部蓝光电影压缩到几Mb甚至几Kb？
如何看待三星Galaxy note10 5G DxO摄像头评测得分113分超华为P30 Pro？
刷完 LeetCode 是什么水平？能拿到什么水平的 offer？
A*寻路是一种广度优先搜索？
在Auto ML的冲击下，ML算法人员是否会在前者成熟后失业的情况？
在电子游戏中99%的暴击率、1%的爆伤和1%的暴击率、99%的爆伤，两者谁带来的收益更高？
如何看待阿里 P8 加面 coding 环节，而 P7 却做不出头条算法题？
请教拓扑排序中的一点疑问？
NSA 在 RSA 加密算法中安置后门是怎么一回事，有何影响？
这张算数入门图（一只兔子加一只兔子）里的题在算什么？