学习面对实际问题如何设计算法与分析算法。
030一般选择问题的算法分析
Loading...
来自 Peking University 的课程
算法设计与分析 Design and Analysis of Algorithms
31 个评分
从本节课中
分治算法的典型应用
在对分治算法有了基本的认识以后，进一步介绍一些典型的分治算法的成功案例，包括各种选择算法、涉及信号降噪处理的卷积计算与快速傅立叶变换、涉及图形学的平面点集凸包的计算等。
与讲师见面
Wanling QuProfessor
School of EECS, Peking University
關於選擇問題，上一講介紹了它的算法設計，是一個分治的算法。
這一講呢，來對上面的算法做分析。
這是上次介紹的偽碼，選擇問題 的偽碼。
在這裡邊呢，它主要的動作是 有遞歸步。
這是原始的選擇問題，它處理的是 S 集合，n 個 元素。
然後我們在產生 m* 的時候，也是這樣的選擇算法。
在 m 這個集合裡頭選中位數，然後當
歸約成子問題以後，進入其中的一個子問題，仍舊是選擇算法。
或者在 S1 中選，或者在 S2 中選，所以它有兩個遞歸調用。
算法的主要工作量，由這兩個遞歸調用的成份來決定。
下面我們看一下，子問題它是遞歸調用 決定它的效率的主要的因素。
那麼在這裡邊，這個子問題究竟有多大呢？我們分別做一下分析。
當用 m* 劃分數組的時候，會出現 下面四個部分。
這一部分的都是不知道 比 m*
大或者小的，這一部分也都是不知道比 m* 大或者小的， 這個部分是比
m* 大的元素，這一部分是比 m* 小的元素。
那我們考慮算法的最壞的情況，就是它歸約以後的子問題盡可能的大。
那這個時候算法的複雜度比歸約以後的子問題小的這個複雜度要高， 那它對應著算法的最壞情況。
下面我們假定它歸約後的子問題達到最大。
最大是什麼情況呢？就是說因為最終我們進入的是一個比 m* 小的， 或者比它大的子問題。
那這兩個呢，我們選擇比較大的情況。
那就是說，比如說我們比 m* 小的元素多，兩個集合的元素和
m* 比了 以後，都是比 m* 小的，全進入這個集合了。
那使得這三部分的元素 構成一個子問題，這對應著算法中一個最壞的情況。
那統計一下這三個集合的元素數，相當於原始規模 n
的大概 多少？我們希望把這個比例算出來。
那做一下計算， 原始的 n 的元素數，是所有這個面積中的元素之和。
那每一列是 5 個元素，一共多少列呢？這邊是 r 個列，
這邊是 r 個列，這塊多出一列出來， 所以總的列數是
兩倍的 r 加上一列，而每列是 5 個元素。
所以這是原始的元素數的所滿足 的公式和這個 r 的關係。
那麼如果這三部份的元素合到一起，構成這個子問題， 一共有多少個元素呢？我們可以來統計一下。
這個元素，這邊是 2 倍的
r， 加上 2r，再加上 3r 加 2。
2 倍的 r 是誰呢？是這個。
因為 這裡邊一共有 r 個列，每列兩個元素。
那麼第二個 2r 是這裡邊的元素，一共有 r 列，每列兩個元素。
而這裡邊的元素呢，每列是 3 個元素， 這是 r 列，3r
加上 2，加上這兩個元素，所以加起來一共是 7 倍的 r 加上
2， 就是子問題最大可以達到 7r 加 2 這個範圍。
而原始的規模呢，是 5 乘以 2r 加 1。
我們就來看一看，這個子問題的規模佔原始規模的多少？ 把它計算出來。
這就是剛才那個公式， 原始的規模是 5 乘以 2r 加 1。
通過這個公式解出 r 和 n 的關係出來，就是
n 除以 5，再減掉 1， 再除 2 就是這個公式。
把它化簡成 十分之n 減掉 二分之一，也就是說 r 大概相當於十分之n大小。
而子問題的規模呢，剛才我們說了， 最壞的情況下，子問題最大達到 7r 加 2。
那把這個 r 用剛才這個值代進入，代進入以後呢，把它化簡，
化簡到十分之7n 減掉二分之三，小於十分之七n。
通過這個分析我們看到，你歸約以後的子問題 就是通過
m* 比較以後，歸約的那個子問題，它最大不超過十分之七n， 不超過原始規模的十分之七。
那有了這個分析以後，我們就可以把工作量 做一下統計了。
整個對於原始問題，規模是 n 的問題，它的
比較次數叫做 W(n)，那在第 2 行就是 每
5 個數，每個組是 5 個數，在這裡邊來找中位數。
那每 5 個數來比較，把它排序的話，也就是常數次的比較次數。
一共多少個組呢？ 是五分之n個組，因此所有的組加起來的工作量是 O(n)。
那通過這個步驟以後，產生了那個 M 集合，在 M 集合裡找中位數。
M 集合是多少？是每個組取一個數，是五分之n個數，
所以 M 集合大小是五分之n，在它裡邊找中位數，用的是同樣選 第 k 小的算法。
那這個工作量就是五分之n 第 k 小算法的工作量應該是
W(n/5)，因為它是遞歸的調用，跟這個算法是一樣的。
那麼劃分，用 m* 來劃分集合，產生那個 S1 和 S2
兩個集合，劃分的工作量呢， 需要有一部份數和 m* 做比較，比較
的元素數不會超過 n，所以這個比較次數是 O(n)。
這個就是遞歸調用進入子問題，剛才已經分析過了，子問題最大也
不超過十分之七n，所以這個工作量不超過 W(7n/10)。
把這些個都加起來，每一行的工作量都加起來，應該 是和這個總工作量相等，那麼總工作量不會超過
這個值，它是一個遞推的方程。
那這是 第 3 行的，這是第 8、 第 9 行的。
這個 O(n) 呢是 第 2 行和第 4 行的這個工作量。
下面我們 看一下這個方程，如果我們考慮成一個方程的時候，這個 O(n) 寫成 c 乘以 n。
用遞歸樹來求解，這是這個方程的 遞歸樹。
那根據這個遞歸樹呢，我們可以看到 這個是它的五分之一，這個是它的十分之七。
我們可以把每一行的量計算出來，這個是 cn， 這個是 0.9
倍的 cn，那麼這 4 項加起來，正好是 0.81 倍 的 cn。
可以觀察出來，下一行是上一行量的 0.9，
它又是它的 0.9，所以我們把所有的，把它加到一起，
總共的工作量應該是不超過這樣的一個級數。
這個級數呢，觀察到它是一個等比的數列， 而且公比是 0.9，是小於 1 的。
因此它收斂到一個常數，整個算法的工作量不超過 O(n)。
這是算法的時間複雜度。
那下邊我們討論一下 當時分組的時候是 5
個元素一組， 如果我們不採用 5 個元素，用 3 個一組，或者
7 個一組，這樣的分組方法行不行呢？ 這裡邊主要影響的是遞歸調用，
因為當你的組的元素少了，比如說3個一組， 那它的組的個數，就是三分之n個組，
就是說這個組的個數就要改變了。
所以你這個 m* 的工作量，當時求 m* 的時候，是在
大 M 集合裡邊來找中位數，所以當你分組的元素數變了以後，
每組的元素數變了以後，增加了這個組的個數 小了
m* 就小了，好，所以影響 這個大 M 集合就小了，因此在計算
m* 的工作量呢， 這個工作量會改變。
那麼 第二個歸約以後的子問題的大小，和分組元素的數也有關係。
如果當這個 t 比較大的時候，這個子問題的規模也會變大。
這就是我們看到的它的影響。
這個影響主要體現在兩個部份， 一個是它的遞歸調用部份，
在這裡邊有兩個跟遞歸調用相關， 一個是 m*
的工作量和大 M 集合的大小相關，
那麼當你分組組內元素數改變的時候， 這個大 M*
的元素數變了，所以你在它裡邊求中位數，這個 時間就變了。
那麼第二項相關的呢，是當你 組的大小不一樣的時候，你最後歸約的子問題的大小也不一樣。
這個組的元素數越多，這個子問題的規模就越大，它會影響這一項的遞歸調用。
由這兩項遞歸調用，它會體現在遞推方程裡面，影響算法的複雜度。
下邊我們討論一下 3 分組的情況，假定元素是 3 個一組，不是 5 個一組，這樣分組。
這樣分組以後，按照 5 個一組的分析方法，它會產生這樣的 4 個集合。
那這 4 個集合的元素數 和原始的 n 有什麼關係呢？來分析一下。
首先這是、 這是 r 列，這是 r 列，加上它是 r 加 1 列，每組 3 個元素。
所以 n 和 r 是這樣的一個公式，然後根據這個
公式呢，我們計算出來 r 和 n 的關係， 可以整理成六分之n
減掉二分之一， 這是反著解出來 r 和 n 的關係。
那麼 子問題的規模達到多大呢？最壞的情況就是這 3 塊
假定都進入同一個子問題，這一共多少 個元素呢？是
4r 加 1 個元素， 就是 1 個 r，2
個 r， 3 個 r， 4 個 r 再加上 1。
那把這個 r 和 n 的關係代進入，可以整理出來是
六分之四n 減 1，就是子問題這規模至多這麼大。
下邊我們就對這個方程求解一下。
這個是遞歸以後的子問題的規模，是 六分之四n，
那這個是求 m* 的，那個大 M 集合的規模是三分之n，
所以有這兩個工作量是遞歸調用， 這邊的 cn 是不變的。
那對於這個方程的解， 你可以通過遞歸樹解出來，這個結果不再是
O(n)，它是一個 nlogn 的函數。
好，為什麼會產生這個情況呢？我們可以觀察到，就是歸約以後的，這個是
三分之n，這個是六分之四n，這兩個子問題的規模加起來， 三分之n，這個實際上是三分之二n，加起來正好是 n。
也就是說，我們每一行，在遞歸樹中每一行的工作量加起來，都是 n。
它不是按照一個 0.9 的一個公比在那縮小， 和 5 分組的情況不一樣。
因此在這個情況下， 一共這棵樹多少層呢？是 logn 個層，就會出現了 nlogn 的結果。
好，那麼，這就體現了分組它會影響算法的
複雜度，要求是你分組以後，遞歸樹的每行的工作量 要構一個成公比小於
1 的等比級數，這個時候算法的複雜度才能是 O(n)。
否則的話，這算法的複雜度可能會增加。
把這個算法小結一下，選第 k 小算法的時間分析，
它是通過遞推方程來分析的是，分組的時候每個元素的多少 會對時間複雜度有影響。
那麼 3 分組是不行的， 5 分組可以， 也可以嘗試一下 7 分組，也是可以的。
所以分組的元素數會影響算法的複雜度。
