如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
有哪些「上帝算法」？递归的本质是什么？
为什么同样是解决一个问题，别人就能想出算法，而我却绞尽脑汁，百般尝试也不得其法？
你写过哪些比较酷的十行以内的 Matlab 代码？
计算机行业是不是自砸饭碗的行业？
MD5哈希算法不可逆，但是网上有很多破译解密哈希密钥的网站，这些都是经过大数据堆积的吗？还是可以破解？
想在业余时间刷leetcode，配合什么书籍/课程/视频网站一起刷leetcode的效率最高？
在知乎你见过哪些明显抱团点反对的问题，对社区有怎样的影响，你有什么好的建议？
将并行计算纳入算法竞赛，是否合适？
可以利用抄代码来同时记忆算法与练英文书法吗？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
正负样本极不平衡的问题？Auto X的自动驾驶技术用了什么技术？
算法书如何选择？
到了 2022 年，人工智能有哪些真正可落地的应用？
中宣部等五部门要求治理算法推荐，不给错误内容提供传播渠道，你认为目前算法推荐存在哪些问题？
在这种不同操作下，对于计算机体系的不同是否会造成时间差异？
有没有手算根号pi的方法？
「贪心算法」的算法思路是什么，它存在什么缺陷？
怎样将一个24的n次方复杂度的计算优化?
大林算法与PID算法有什么本质区别?
如何评价Google 在TensorFlow 中引入的bfloat16 数据类型？
各种机器学习算法的应用场景分别是什么（比如朴素贝叶斯、决策树、K 近邻、SVM、逻辑回归最大熵模型）？
在一个非常繁忙的十字路口，红绿灯坏了，请问无人驾驶汽车能顺利通过吗？
比特币的算法到底在算什么？
有哪些算法惊艳到了你？
为什么技术主管跟我说程序员学算法不是最重要的，从工作项目中学习实际才是最重要的？
智能座舱的算法包括哪些方面？
有什么算法可以很快的找出所有完全对称日呢?
2021-05-28：跳跃游戏 II。给定一个非负整数数组，你最初位于数组的第一个位...如何解答呢？
如何看待 2022 年秋招算法岗竞争如此激烈？
有哪些「上帝算法」？
如何激怒一位计算机科学爱好者？
是否存在一个函数，使得它的逆运算是容易求的，而它的逆运算的逆运算是难求的？
刷完 LeetCode 是什么水平？能拿到什么水平的 offer？
程序员不需要知道太多数学，你认同吗？
各种机器学习算法的应用场景分别是什么（比如朴素贝叶斯、决策树、K 近邻、SVM、逻辑回归最大熵模型）？
有什么算法可以很快的找出所有完全对称日呢?
有什么算法可以很快的找出所有完全对称日呢?
如何判断这两份代码的时间复杂度？
要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？