麻省理工學(xué)院公開課：算法導(dǎo)論耳鸯。B站地址，網(wǎng)易公開課也有對應(yīng)的資源创译。
https://www.bilibili.com/video/av1149902/?p=6
本節(jié)課的主要內(nèi)容是抵知，講解順序統(tǒng)計問題的兩個算法，兩個算法都是線性時間的软族。第一個算法是隨機(jī)的刷喜，所以只是期望時間是線性時間。第二個算法以第一個算法為基礎(chǔ)立砸，考慮其最壞情況掖疮。

這節(jié)課不再看排序問題了，看其它的也是線性時間的問題颗祝。寫算法5分鐘浊闪，分析2小時。(⊙v⊙)

問題：在一個長度為n的無序數(shù)組中螺戳，找到第k小的元素（即排名第k的元素）
思考：如果是已排序的數(shù)組搁宾，就可以直接找到索引為k的元素了。但是這里不允許排序哦倔幼。
方案一：排序盖腿，并返回第k個元素。如果使用歸并排序损同，那么時間復(fù)雜度為nlgn翩腐。但是我們希望有比nlgn更好的算法。

分析：
k的取值范圍是(0, n)
k=1揖庄，即找到數(shù)組中的最小值栗菜，那么最直接的做法是遍歷整個數(shù)組欠雌，找到最小值保存即可蹄梢，時間復(fù)雜度為n。
k=n富俄，即最大值禁炒，同上。
k=(n+1)/2或者(n-1)/2霍比，即中位數(shù)幕袱。這個相比前面兩個就沒那么容易求得了，也就比較有意思了【?? 這節(jié)課的主要內(nèi)容也是求中位數(shù)悠瞬。其實(shí)可以算k為任何值的情況们豌，但這里找個中位數(shù)作為代表即可涯捻。

隨機(jī)的分治算法

隨機(jī)選擇

Rand-Select(A, p, q, i)
A表示數(shù)組，這里不在整個數(shù)組中查找望迎，只從p和q這一段里面查找障癌，因?yàn)橐褂眠f歸，i表示要查找的索引辩尊。

• 基礎(chǔ)情況：if p==q return A[p]
• 這里要使用部分快排的內(nèi)容涛浙， r <- Rand-Partition(A, p, q) 表示在數(shù)組A中的p到q之間，隨機(jī)找個數(shù)摄欲，和第一個元素交換轿亮，再調(diào)用劃分函數(shù)，劃分函數(shù)用第一個元素將數(shù)組分成兩部分胸墙。一部分內(nèi)的元素都小于等于第一個劃分元素我注，另一部分大于等于劃分元素。在p和q之間隨機(jī)選一個劃分迟隅，將數(shù)組分成可能不相等的兩部分仓手。A[r]是劃分元素，r是劃分元素的位置玻淑。
• 在r前面有r-p+1個元素（包括r）嗽冒。如果從p開始算起，劃分元素的序號為k <- r-p+1补履，A[k]在A[p...q]之間添坊。

• 接下來是遞歸，根據(jù)i和k的關(guān)系箫锤，有三種情況贬蛙。【i是我們要找的序號谚攒，k是我們劃分元素在調(diào)用劃分函數(shù)之后對應(yīng)的位置阳准。
  如果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帮寻。

這里總的工作量為：劃分函數(shù)需要線性時間乍狐，這里只進(jìn)行了一次遞歸。分析下這里的總運(yùn)行時間固逗，先看看最好的情況和最壞的情況浅蚪。

這里有個大前提藕帜，假設(shè)所有的元素都是不相等的。如果有相等的元素惜傲，就會有點(diǎn)亂耘戚，甚至得修改一下算法。因?yàn)槿绻械脑囟枷嗟炔倌x擇一個隨機(jī)元素收津，劃分效果就很差。

最好的情況是正中劃分浊伙，就是正好把數(shù)組分成了兩半一樣的大小撞秋，左邊的元素數(shù)量和右邊的元素數(shù)量相等。不過1/10:9/10的劃分也不錯嚣鄙，任何常數(shù)比例的劃分都和正中劃分一樣是可以的吻贿。
如果是1/10:9/10的劃分，遞歸表達(dá)式為T(n) ≤ T(9/10·n)+Θ(n)哑子，大多數(shù)情況下應(yīng)該會被劃分在9/10中舅列，這算是在幸運(yùn)的情況中做最壞情況的分析。
使用主方法求解遞歸式T(n) = T(9/10·n)+Θ(n)卧蜓，其中f(n) = n帐要，n^log_ba = n⁰ = 1。輸入主方法的第三種情況弥奸，所以T(n) = Θ(n)

最壞情況每次選中的劃分元素都是最邊界的元素榨惠。如劃分后的區(qū)間為(0, n-1)。遞歸表達(dá)式為T(n) = T(n-1) + Θ(n)盛霎，這是一個等差級數(shù)赠橙，其時間復(fù)雜度為Θ(n²)【前面的課程也有分析過】。但是這種情況一般不會出現(xiàn)愤炸，就像每次拋硬幣都輸一樣期揪，概率非常低。

分析其期望運(yùn)行時間规个。這是一個分治算法凤薛，所以先寫出關(guān)于運(yùn)行時間的遞歸式。分析的第一步绰姻，先看看有哪些不同的情況枉侧。這里有很多種劃分的可能引瀑，對半劃分或者劃分到了邊界如(0, n-1)的情況狂芋，一共有n種劃分的可能。
如何分析這么多的情況呢憨栽？指示器隨機(jī)變量帜矾。指示器隨機(jī)變量表示翼虫，我們不只是處理函數(shù)T(n)，而且是一個隨機(jī)變量屡萤。T(n)依賴隨機(jī)選擇珍剑，所以它是一個隨機(jī)變量。

T(n)是算法在規(guī)模為n的情況下的運(yùn)行時間死陆，這里要明確地寫出關(guān)于隨機(jī)數(shù)的假設(shè)招拙，即它們的選擇是相互獨(dú)立的。也就是每次調(diào)用劃分函數(shù)的時候措译，得到的結(jié)果都是獨(dú)立于其它時候調(diào)用的結(jié)果的别凤。

指示器隨機(jī)變量的定義：X_k，其中k∈{0, 1, ... , n-1}

• X_k = 1领虹，if 劃分結(jié)果為k:(n-k-1)
• X_k = 0规哪，else

窮舉所有隨機(jī)劃分的情況如下：
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) )] -----//因?yàn)镋[X_k] = 1/n最疆，快排一集中有講
........... = (1/n) Σ E[T(max{k, n-k-1})] + (1/n) Σ E[Θ(n)]

以上的Σ表示從 k=0,1,2,3,...,n-1 累加的情況杯巨。

這里和隨機(jī)快速排序不同，因?yàn)檫@里要處理函數(shù)max努酸，隨機(jī)快速排序求的是T(k)加T(n-k-1)的和舔箭，因?yàn)楫?dāng)時要使函數(shù)在兩組數(shù)據(jù)上同時遞歸。但是這里只需要求長的一組數(shù)據(jù)蚊逢，所以需要考慮怎么處理max层扶。
只要對其中的一半依次求和，然后乘2烙荷，因?yàn)檫@里每個項(xiàng)都出現(xiàn)了兩次镜会。如k=0和k=n-1，這里max的值均為T(n-1)终抽，所以只需要計算這個求和式里一半的項(xiàng)戳表。其中n可能為奇數(shù)，那n/2就多算了一位昼伴，所以下面為小于等于匾旭。

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

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

如果求解這個遞歸式呢价涝？這里使用代換法來解遞歸式。不能用主定理持舆，因?yàn)槊恳淮芜f歸色瘩，k的值都是在變化的伪窖，而主定理要求k的值是固定不變的。

代換法求解期望值遞歸式

1居兆、先做一個假設(shè)覆山，這個遞歸式的運(yùn)行時間是線性的，即E[T(n)] ≤ cn泥栖，其中c是足夠大的常數(shù)簇宽。
2、驗(yàn)證
E[T(n)] ≤ (2/n) Σ E[T(k)] + Θ(n)
........... ≤ (2/n) Σ ck + Θ(n) --------//根據(jù)歸納假設(shè)（吧享？）晦毙，E[T(k)] ≤ ck
........... = (2c/n) Σ k + Θ(n)
........... ≤ (2c/n) (3/8)n² + Θ(n) --------//Σ k ≤ (3/8)n²
........... = cn - ((1/4)cn - Θ(n))
存在足夠大的c，使得余項(xiàng)((1/4)cn - Θ(n))≥0耙蔑，所以E[T(n)] ≤ cn

即隨機(jī)選擇算法（Rand-Select）的期望運(yùn)行時間為Θ(n)见妒，在非常unlucky的情況下才會是Θ(n²)。那如何避免出現(xiàn)Θ(n²)的情況呢甸陌？

線性的最壞情況時間復(fù)雜度

保證每次取到的都是一個好的主元（劃分元素）须揣，【遞歸地生成主元，如何遞歸地生成也是個問題钱豁，因?yàn)檫@個過程的時間復(fù)雜度不能超過線性】
Select(i, n)耻卡，這是一個比較老的算法，由幾個人一起發(fā)明的牲尺。
1卵酪、把n個元素分成(n/5)組大小為5的網(wǎng)格，其中n/5向下取整谤碳。找出每一組元素的中值溃卡。這里的時間復(fù)雜度為Θ(n)。

中間方框圈出的為每一組元素的中值

2蜒简、遞歸瘸羡，在這(n/5)組元素的中值中再求中值，時間復(fù)雜度為T(n/5)

中間兩個框框的元素是中值中的中值

3搓茬、根據(jù)上一步犹赖，找到劃分元素x，其中k=rank(x)卷仑，k是x的排序號峻村，這里的時間復(fù)雜度為Θ(n)。
4锡凝、同上面的隨機(jī)選擇一樣的判斷粘昨，求解這里的時間復(fù)雜度。上面已經(jīng)有個T(n/5)的遞歸，所以這里的遞歸常數(shù)最好小于4/5雾棺。
if i==k return x
if i<k return 左邊遞歸
if i>k return 右邊遞歸

用圖來求解上面的遞歸常數(shù)膊夹。下面是一個標(biāo)記衬浑，a有一個箭頭指向b捌浩，表示a<b。

根據(jù)標(biāo)記畫出的指向圖如下：

補(bǔ)充幾個中值的指向：

傳遞性

可以發(fā)現(xiàn)左下角的方塊一整塊都是小于x的工秩，而右上角的方塊是大于x的

左下角的方塊尸饺，包含了一半的列，以及3/5的行助币，也就是至少有3(1/2)(n/5)個元素≤x浪听，即(3/10)n向下取整。右上角的方塊也一樣眉菱，所以不等式的兩邊至少各有(3/10)n個元素迹栓，因此不等號的兩邊最多有(7/10)n個元素。所以上面第四步的遞歸常數(shù)為7/10俭缓，比4/5好克伊。

把向下取整的符號去掉，(3/10)/n向下取整 > n/4（這里取底為4是為了方便計算）华坦。即每一組至少有n/4個元素愿吹，即不等號的另一邊最多有(3/4)n個元素。而1/5小于1/4惜姐，所以加起來的時間復(fù)雜度小于n犁跪。

上面幾個步驟加起來的時間復(fù)雜度：T(n) ≤ T(n/5) + T(3n/4) + Θ(n)
使用代換法證明上面這個遞歸表達(dá)式的時間復(fù)雜度是線性的
1、假設(shè)T(n) ≤ cn
2歹袁、T(n) ≤ cn/5 + 3cn/4 + Θ(n)
............ = (19/20)cn + Θ(n)
............ = cn - ((1/20)cn - Θ(n))
存在足夠大的c坷衍，使得余項(xiàng)(1/20)cn - Θ(n) > 0成立。

課后練習(xí)

為什么這里要使用5來分組条舔，而不是3呢惫叛？【5是這個算法能成功的最小整數(shù)