關於選擇問題,上一講介紹了它的算法設計,是一個分治的算法。
這一講呢,來對上面的算法做分析。
這是上次介紹的偽碼,選擇問題 的偽碼。
在這裡邊呢,它主要的動作是 有遞歸步。
這是原始的選擇問題,它處理的是 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 分組,也是可以的。
所以分組的元素數會影響算法的複雜度。