如何证明快速排序法的平均复杂度为 O(nlogn)？ 第1页
1
网友的相关建议:
其实这个可以求精确解的吧.
直接设对规模 的数组排序需要的时间期望为 , 期望其实就是平均复杂度换个说法.
随手写个快排:
qs [{}] = {}; qs [{ x_ , xs___ }] := Join [ qs @ Select [{ xs }, # <= x & ],{ x }, qs @ Select [{ xs }, # > x & ]]; 空表的时候不用排, 所以初值条件就是 .
所谓快排就是随便取出一个数,一般是第一个数,然后小于等于他的放左边, 大于他的的排右边.
比如左边 个那接下来还要排: 的时间.
然后 多少那是不确定的, 遍历 , 出现概率都是相等的.
另外分割操作本身也要时间 , 操作花费是线性时间 , 这也要加进去, 所以一共是:
注意和式展开就是 到 加了两遍
然后就是喜闻乐见的解递推了:
这个一阶非线性齐次差分方程的解是:
嗯, 所以确切的说快排算法的小常数是两倍的分割速度.
让函数在无穷远处展开
最高阶是 所以就是 了.
1
相关话题
一个N*N的矩阵，取值为0或1，有什么好的算法判断一行或一列全为1啊？怎样将一个24的n次方复杂度的计算优化?
给人指路，说左右和说东西南北在算法上哪个更优？
有哪些令人拍案叫绝的算法？
要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？
算法老师劝学生放弃学习 JavaScript，我该怎么办？
计算复杂性理论是否具有足够的现实意义，如今有哪些比较「现实」的应用？
python怎么去掉最大值和最小值，怎么找到最大值与最小值，去掉最大值最小值比如下面这道题?
如何高效地获得玩家排名？
在知乎你见过哪些明显抱团点反对的问题，对社区有怎样的影响，你有什么好的建议？
前一个讨论
英文论文写作时，公式推导那块如何写作？
下一个讨论
有没有那种小到极致的表情包啊?
相关的话题
开发人员如何构建自己的学习笔记系统？刷完 LeetCode 是什么水平？能拿到什么水平的 offer？
0x5f3759df这个快速开方中的常数的数学依据是什么？
我们高中数学为什么不重视算法？高中学的数列，三角函数，求导，圆锥曲线相关问题的解法和算法有什么关系？
学物理为什么会觉得计算机很难？
计算机视觉（CV）的算法有哪些，具体都有哪些特点？
二分查找有几种写法？它们的区别是什么？
我们高中数学为什么不重视算法？高中学的数列，三角函数，求导，圆锥曲线相关问题的解法和算法有什么关系？
数字图像处理的工作是用传统算法更多还是用深度学习更多?
为什么很多程序无法计算负数的立方根？
如何评价教育部发文：AI、算法等2018年进入全国高中课程？
你靠哪些讲解学会了曾经怎么也学不会的算法？
到了 2022 年，人工智能有哪些真正可落地的应用？
要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？
有没有手算根号pi的方法？
如何看待滴滴章文嵩称，滴滴面临的问题比 AlphaGo 复杂 100 倍？
一个算法面试题，怎么写？
哪位大佬能来个骨灰级的红黑树讲解啊？
对于编程思想和能力有重大提升的书有哪些?
如何证明快速排序法的平均复杂度为 O(nlogn)？
非计算机专业，想刷leetcode，请问在此之前需要做什么准备？
如何看待快手 CEO 宿华发文称，将用正确的价值观指导算法？
为什么说 MD5 是不可逆的？
如何评价百度自动驾驶 ApolloAuto 在 Github 上发布的代码？
天天P图中我的小学生证件照功能怎么实现的？算法是什么样？
哪位大佬能给我详细解答下AHP灰色综合评价模型的原理和算法啊，不胜感激！？
为什么梯度下降能找到最小值？
cpp是不是最方便研究算法的语言？
如何看待关于“数据结构与算法基础”的重要性？
沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌 ）是怎样的？