如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
美剧《硅谷》第三季第一集神秘代码写的是什么？如何系统学习机器学习？
你在生活中用过最高级的算法知识是什么？
任何密码都可以用穷举推算出来，只是时间问题。如果是这样的话，那不是很不安全？
如果按国家分，哪个国家编程最厉害？有没有代表人物？
智能座舱的算法包括哪些方面？
如何看待 2020 届校招算法工程师岗位求职人数远大于招聘岗位的现象？
平滑的战争迷雾效果是如何实现的？
能否使用神经网络来判断奇偶数？
如果一个算法空间复杂度是指数级，时间复杂度是多项式级，那么这个算法复杂度怎么算呢？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
如何用简单易懂的例子解释隐马尔可夫模型？如果一个算法空间复杂度是指数级，时间复杂度是多项式级，那么这个算法复杂度怎么算呢？
在知乎你见过哪些明显抱团点反对的问题，对社区有怎样的影响，你有什么好的建议？
怎样将一个24的n次方复杂度的计算优化?
如果按国家分，哪个国家编程最厉害？有没有代表人物？
如何编程判断一个数是否是质数？
微信红包的随机算法是怎样实现的？
如何看待 2020 届校招算法工程师岗位求职人数远大于招聘岗位的现象？
机器学习小白来提问：关于联邦学习FedAVG和FedSGD的问题？
如何激怒一位计算机科学爱好者？
如何评价姜新文老师提出的NP=P这篇文章？
算法书如何选择？
这张算数入门图（一只兔子加一只兔子）里的题在算什么？
如果某一天证实随机数根本就不存在，会对生活的各个领域产生什么样的影响？
程序员应该如何学习算法？
怎样实现浮点数除以一个数再乘以这个数结果等于原值?
感觉算法在程序员中快被吹上天了，如果只是搞编程的话，是不是没必要死磕算法？
如何看待 2021 年图灵奖授予美国计算机科学家 Jack J. Dongarra?
程序员必须掌握哪些算法？
假如我知道了抽卡游戏的随机数生成算法源码，是否能成为欧皇？
负数与负数相乘为什么会得正？
RSA的公钥和私钥到底哪个才是用来加密和哪个用来解密？
卡尔曼滤波器是如何运用于多传感器融合的？
一个程序员的水平能差到什么程度?
如何把梯度传递过Argmax?
100个金币，只有1个略重，其余99个一样重。给你一个天平，最少称几次能确保找出那个略重的?
怎样实现浮点数除以一个数再乘以这个数结果等于原值?
中国目前的人工智能在全球处于什么水平？
能否通过计算机找到适合速拧的魔方解法？
有没有可能让计算机去理解代码，从而写代码？