如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
类似微博的 feed 热度算法如何计算？算法工程师如何应对做算法策略的不确定性；比如没效果，这时绩效怎么保证？
为什么梯度下降能找到最小值？
RSA的公钥和私钥到底哪个才是用来加密和哪个用来解密？
RSA的公钥和私钥到底哪个才是用来加密和哪个用来解密？
蒙特卡罗算法是什么？
Auto X的自动驾驶技术用了什么技术？
想学好计算机算法，是否需要重新学数学呢?
是否存在一个函数，使得它的逆运算是容易求的，而它的逆运算的逆运算是难求的？
刷完 LeetCode 是什么水平？能拿到什么水平的 offer？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
能否详细说明一下对称算法中的DES,AES?如何判断这两份代码的时间复杂度？
你写过什么有趣的程序？
Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异？
如何简单形象又有趣地讲解神经网络是什么？
如何利用群论的知识解决三阶魔方？
李彦宏批评推荐式算法，你怎么看？
很多高效排序算法的代价是 nlogn，难道这是排序算法的极限了吗？
到了 2022 年，人工智能有哪些真正可落地的应用？
如何看待快手 CEO 宿华发文称，将用正确的价值观指导算法？
RSA的公钥和私钥到底哪个才是用来加密和哪个用来解密？
为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？
你写过哪些比较酷的十行以内的 Matlab 代码？
cv/nlp等方向的就业困难是全球性的吗？
如何评价b站up主图灵的猫关于tiktok的视频？
你为什么要学算法？
递归的本质是什么？
想在业余时间刷leetcode，配合什么书籍/课程/视频网站一起刷leetcode的效率最高？
如何评价教育部发文：AI、算法等2018年进入全国高中课程？
如何面对算法竞赛的焦虑？
为什么梯度下降能找到最小值？
如何判断这两份代码的时间复杂度？
[题]两个数的最小公倍数是36，最大公因数是6，这两个数可能是多少？
C++笔试算法题允许用stl函数吗？
求十亿内所有质数的和，怎么做最快?
对于任意既约分数，都可以分解成有限个不同奇数的倒数和吗？
「数据结构」的主要内容有哪些，难度如何，怎样系统地学习？
从一读到一亿需要读多少个汉字？
如何直观地解释 backpropagation 算法？
学习算法有什么入门级的书 ? 或者学习资料。(英语不太好)