麻省理工学院公开课：算法导论。B站地址，网易公开课也有对应的资源。
https://www.bilibili.com/video/av1149902/?p=6
本节课的主要内容是，讲解顺序统计问题的两个算法，两个算法都是线性时间的。第一个算法是随机的，所以只是期望时间是线性时间。第二个算法以第一个算法为基础，考虑其最坏情况。

这节课不再看排序问题了，看其它的也是线性时间的问题。写算法5分钟，分析2小时。(⊙v⊙)

问题：在一个长度为n的无序数组中，找到第k小的元素（即排名第k的元素）
思考：如果是已排序的数组，就可以直接找到索引为k的元素了。但是这里不允许排序哦。
方案一：排序，并返回第k个元素。如果使用归并排序，那么时间复杂度为nlgn。但是我们希望有比nlgn更好的算法。

分析：
k的取值范围是(0, n)
k=1，即找到数组中的最小值，那么最直接的做法是遍历整个数组，找到最小值保存即可，时间复杂度为n。
k=n，即最大值，同上。
k=(n+1)/2或者(n-1)/2，即中位数。这个相比前面两个就没那么容易求得了，也就比较有意思了【😯 这节课的主要内容也是求中位数。其实可以算k为任何值的情况，但这里找个中位数作为代表即可。

随机的分治算法

随机选择

Rand-Select(A, p, q, i)
A表示数组，这里不在整个数组中查找，只从p和q这一段里面查找，因为要使用递归，i表示要查找的索引。

• 基础情况：if p==q return A[p]
• 这里要使用部分快排的内容， r <- Rand-Partition(A, p, q) 表示在数组A中的p到q之间，随机找个数，和第一个元素交换，再调用划分函数，划分函数用第一个元素将数组分成两部分。一部分内的元素都小于等于第一个划分元素，另一部分大于等于划分元素。在p和q之间随机选一个划分，将数组分成可能不相等的两部分。A[r]是划分元素，r是划分元素的位置。
• 在r前面有r-p+1个元素（包括r）。如果从p开始算起，划分元素的序号为k <- r-p+1，A[k]在A[p...q]之间。

• 接下来是递归，根据i和k的关系，有三种情况。【i是我们要找的序号，k是我们划分元素在调用划分函数之后对应的位置。
  如果i==k，那么就是我们要找的元素。if r==k return A[r]
  if i<k，return Rand-Select(A, p, r-1, i)
  if i>k，return Rand-Select(A, r+1, q, i-k)。注意，这里递归右边部分的时候需要对i的位置做一下偏移，就是减掉左边的长度k。

这里总的工作量为：划分函数需要线性时间，这里只进行了一次递归。分析下这里的总运行时间，先看看最好的情况和最坏的情况。

这里有个大前提，假设所有的元素都是不相等的。如果有相等的元素，就会有点乱，甚至得修改一下算法。因为如果所有的元素都相等，选择一个随机元素，划分效果就很差。

最好的情况是正中划分，就是正好把数组分成了两半一样的大小，左边的元素数量和右边的元素数量相等。不过1/10:9/10的划分也不错，任何常数比例的划分都和正中划分一样是可以的。
如果是1/10:9/10的划分，递归表达式为T(n) ≤ T(9/10·n)+Θ(n)，大多数情况下应该会被划分在9/10中，这算是在幸运的情况中做最坏情况的分析。
使用主方法求解递归式T(n) = T(9/10·n)+Θ(n)，其中f(n) = n，n^log_ba = n⁰ = 1。输入主方法的第三种情况，所以T(n) = Θ(n)

最坏情况每次选中的划分元素都是最边界的元素。如划分后的区间为(0, n-1)。递归表达式为T(n) = T(n-1) + Θ(n)，这是一个等差级数，其时间复杂度为Θ(n²)【前面的课程也有分析过】。但是这种情况一般不会出现，就像每次抛硬币都输一样，概率非常低。

分析其期望运行时间。这是一个分治算法，所以先写出关于运行时间的递归式。分析的第一步，先看看有哪些不同的情况。这里有很多种划分的可能，对半划分或者划分到了边界如(0, n-1)的情况，一共有n种划分的可能。
如何分析这么多的情况呢？指示器随机变量。指示器随机变量表示，我们不只是处理函数T(n)，而且是一个随机变量。T(n)依赖随机选择，所以它是一个随机变量。

T(n)是算法在规模为n的情况下的运行时间，这里要明确地写出关于随机数的假设，即它们的选择是相互独立的。也就是每次调用划分函数的时候，得到的结果都是独立于其它时候调用的结果的。

指示器随机变量的定义：X_k，其中k∈{0, 1, ... , n-1}

• X_k = 1，if 划分结果为k:(n-k-1)
• X_k = 0，else

穷举所有随机划分的情况如下：
T(n) = T(max{0,n-1}) + Θ(n)，if 划分为0:n-1
T(n) = T(max{1,n-2}) + Θ(n)，if 划分为1:n-2
...
T(n) = T(max{n-1,0}) + Θ(n)，if 划分为n-1:0
即：
T(n) = Σ X_k( T(max{k, n-k-1}) + Θ(n) )，k=0,1,2,...n-1

T(n)的期望值

E[T(n)] = E[Σ X_k( T(max{k, n-k-1}) + Θ(n) )]
........... = Σ E[X_k( T(max{k, n-k-1}) + Θ(n) )]
........... = Σ E[X_k] · E[( T(max{k, n-k-1}) + Θ(n) )]
........... = (1/n) Σ E[( T(max{k, n-k-1}) + Θ(n) )] -----//因为E[X_k] = 1/n，快排一集中有讲
........... = (1/n) Σ E[T(max{k, n-k-1})] + (1/n) Σ E[Θ(n)]

以上的Σ表示从 k=0,1,2,3,...,n-1 累加的情况。

这里和随机快速排序不同，因为这里要处理函数max，随机快速排序求的是T(k)加T(n-k-1)的和，因为当时要使函数在两组数据上同时递归。但是这里只需要求长的一组数据，所以需要考虑怎么处理max。
只要对其中的一半依次求和，然后乘2，因为这里每个项都出现了两次。如k=0和k=n-1，这里max的值均为T(n-1)，所以只需要计算这个求和式里一半的项。其中n可能为奇数，那n/2就多算了一位，所以下面为小于等于。

以下的Σ表示从 k=n/2,...,n-1 累加的情况，其中n/2向下取整。

（接上面的计算）
........... ≤ (2/n) Σ E[T(k)] + Θ(n)

如果求解这个递归式呢？这里使用代换法来解递归式。不能用主定理，因为每一次递归，k的值都是在变化的，而主定理要求k的值是固定不变的。

代换法求解期望值递归式

1、先做一个假设，这个递归式的运行时间是线性的，即E[T(n)] ≤ cn，其中c是足够大的常数。
2、验证
E[T(n)] ≤ (2/n) Σ E[T(k)] + Θ(n)
........... ≤ (2/n) Σ ck + Θ(n) --------//根据归纳假设（？），E[T(k)] ≤ ck
........... = (2c/n) Σ k + Θ(n)
........... ≤ (2c/n) (3/8)n² + Θ(n) --------//Σ k ≤ (3/8)n²
........... = cn - ((1/4)cn - Θ(n))
存在足够大的c，使得余项((1/4)cn - Θ(n))≥0，所以E[T(n)] ≤ cn

即随机选择算法（Rand-Select）的期望运行时间为Θ(n)，在非常unlucky的情况下才会是Θ(n²)。那如何避免出现Θ(n²)的情况呢？

线性的最坏情况时间复杂度

保证每次取到的都是一个好的主元（划分元素），【递归地生成主元，如何递归地生成也是个问题，因为这个过程的时间复杂度不能超过线性】
Select(i, n)，这是一个比较老的算法，由几个人一起发明的。
1、把n个元素分成(n/5)组大小为5的网格，其中n/5向下取整。找出每一组元素的中值。这里的时间复杂度为Θ(n)。

中间方框圈出的为每一组元素的中值

2、递归，在这(n/5)组元素的中值中再求中值，时间复杂度为T(n/5)

中间两个框框的元素是中值中的中值

3、根据上一步，找到划分元素x，其中k=rank(x)，k是x的排序号，这里的时间复杂度为Θ(n)。
4、同上面的随机选择一样的判断，求解这里的时间复杂度。上面已经有个T(n/5)的递归，所以这里的递归常数最好小于4/5。
if i==k return x
if i<k return 左边递归
if i>k return 右边递归

用图来求解上面的递归常数。下面是一个标记，a有一个箭头指向b，表示a<b。

根据标记画出的指向图如下：

补充几个中值的指向：

传递性

可以发现左下角的方块一整块都是小于x的，而右上角的方块是大于x的

左下角的方块，包含了一半的列，以及3/5的行，也就是至少有3(1/2)(n/5)个元素≤x，即(3/10)n向下取整。右上角的方块也一样，所以不等式的两边至少各有(3/10)n个元素，因此不等号的两边最多有(7/10)n个元素。所以上面第四步的递归常数为7/10，比4/5好。

把向下取整的符号去掉，(3/10)/n向下取整 > n/4（这里取底为4是为了方便计算）。即每一组至少有n/4个元素，即不等号的另一边最多有(3/4)n个元素。而1/5小于1/4，所以加起来的时间复杂度小于n。

上面几个步骤加起来的时间复杂度：T(n) ≤ T(n/5) + T(3n/4) + Θ(n)
使用代换法证明上面这个递归表达式的时间复杂度是线性的
1、假设T(n) ≤ cn
2、T(n) ≤ cn/5 + 3cn/4 + Θ(n)
............ = (19/20)cn + Θ(n)
............ = cn - ((1/20)cn - Θ(n))
存在足够大的c，使得余项(1/20)cn - Θ(n) > 0成立。

课后练习

为什么这里要使用5来分组，而不是3呢？【5是这个算法能成功的最小整数