如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
如何证明一个数 n 的因子之和是 O(n) 的？如何直接跳出深层递归而不是一层一层跳出？
为什么得不到「自由意志」会让那么多人难以接受？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
如何看待阿里 P8 加面 coding 环节，而 P7 却做不出头条算法题？
目标检测算法中Two-stage算法速度慢,到底在哪里?
如何看待网传字节跳动 28 岁图像算法工程师心梗猝死？还有 30 年房贷没还完，可以退房退款吗？
如何看待网传字节跳动 28 岁图像算法工程师心梗猝死？还有 30 年房贷没还完，可以退房退款吗？
Cambridge Analytica 是一家怎样的公司？
QR 二维码在不影响扫码的情况下，哪些部分可以删除？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
李彦宏批评推荐式算法，你怎么看？有哪些令人拍案叫绝的算法？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
为什么得不到「自由意志」会让那么多人难以接受？
学了四年算法，码了五万行代码，但是大一期末C语言模拟及不了格怎么办？
Cambridge Analytica 是一家怎样的公司？
能否详细说明一下对称算法中的DES,AES?
有什么理论复杂但是实现简单的算法？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
我发现设计模式一个很奇妙的情况，不知各位知友遇过没？
算法导论求有向图强连通分量：按拓扑排序，求反向图的DFS。若改成按拓扑排序倒序，用原图做DFS，错在哪？
一个算法面试题，怎么写？
在电子游戏中99%的暴击率、1%的爆伤和1%的暴击率、99%的爆伤，两者谁带来的收益更高？
面试题:一个长度为n的数组，其中数组中每个元素的值都不大于n，如何用O(n)的算法判断数组中是否存在重复元素?
如何学习视频识别技术？
一个单链表，长度未知，如何快速的找出位于中间的那个元素？
对 n × n 网格图，从左下角走到右上角的边不重复路径（即左下角到右上角的迹）有多少种？
cpp是不是最方便研究算法的语言？
有没有必要把机器学习算法自己实现一遍？
如何用一个1-8随机数生成器制作一个1-7随机数生成器？
如何评价 2021 年 ICPC 银川赛区？
有什么算法可以很快的找出所有完全对称日呢?
如何激怒一位计算机科学爱好者？
可以利用抄代码来同时记忆算法与练英文书法吗？
怎样将一个24的n次方复杂度的计算优化?
[题]两个数的最小公倍数是36，最大公因数是6，这两个数可能是多少？
有没有可能让计算机去理解代码，从而写代码？
程序员必须掌握哪些算法？
Size Balanced Tree 真的是国内 ACM 选手陈启峰的发明吗？
只需4组数据，还原你的购物模式，具体算法是怎么实现的？