如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
如何看待快手 CEO 宿华发文称，将用正确的价值观指导算法？如何计算一局三国杀所进行的回合数的数学期望？
关于算法导论定理3.1，为什么感觉快速排序的时间复杂度不满足这个定理？
算法岗位真的需要顶会才能入场吗？
如何检验算法的正确性？
如何证明快速排序法的平均复杂度为 O(nlogn)？
什么是机器学习？
Learning To Rank的pair wise方法如何得到全局排序结果呢？
大家都见过哪些让你虎躯一震的代码？
公民身份号码有可能是素数吗？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
怎样实现浮点数除以一个数再乘以这个数结果等于原值?「贪心算法」的算法思路是什么，它存在什么缺陷？
有哪些数学定理或者数学知识惊呆了你？
如何激怒一位计算机科学爱好者？
有哪些手算对数的方法？
类似微博的 feed 热度算法如何计算？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
用 C# 写个方法解析简单的 JSON 字符串有哪些思路？
DeepMind 再登 Nature，用 AI 破译古希腊文字，该成果会对人类历史研究带来什么影响？
有什么理论复杂但是实现简单的算法？
为什么算法时间复杂度没有三角函数级别？
如何评价 2021 年 ICPC 银川赛区？
cpp是不是最方便研究算法的语言？
如何理解计算物理中的元胞链接列表（Cell Linked List）算法？
怎样衡量一个机器学习工程师对算法的掌握程度？
机器学习小白来提问：关于联邦学习FedAVG和FedSGD的问题？
EM算法存在的意义是什么？
ICLR 2019 有什么值得关注的亮点？
有没有能向玩家保证服务器发牌时没有作弊的牌类游戏发牌算法？
非CS背景，如何快速上手机器学习？
苹果的 Differential Privacy 差分隐私技术是什么原理？
戴克斯特拉算法（Dijkstra）的本质是贪心，还是动态规划？
为什么根据数组下标获取数据时间是一样的，难道下标不用寻址吗？
算法工程师的落地能力具体指的是什么？
掷一枚不均匀的硬币，正面概率为0.7，反面的概率为0.3，如何最高效地获得一个概率为0.5的事件？
为什么说 MD5 是不可逆的？
平滑的战争迷雾效果是如何实现的？
推荐系统有什么危害?
为什么下面程序递归计算斐波那契数列java比c++要快？
哪位大佬能来个骨灰级的红黑树讲解啊？