動機
分治算法會在當前輸入上花費一部分工作量,再求解規模較小的子問題,並合併它們的答案。遞歸樹按深度把總工作量分開計算。視乎子問題個數與子問題規模縮小速度之間的比較,根、葉或各層合在一起都可能主導總代價。
這裏的結果是一個刻意加以限制的主定理:各子問題的規模恰好相等,附加代價是正常數乘以某個冪,而且輸入規模是除數的冪。向下取整與向上取整的影響、規模不等的子問題以及帶對數的附加代價,都需要另行論證。這些限制令計算精確,並顯示了三種情形為何出現。
定義
固定整數 a ≥ 1 a\ge1 a ≥ 1 與 b ≥ 2 b\ge2 b ≥ 2 ,實數 d ≥ 0 d\ge0 d ≥ 0 ,以及常數 c , t 0 > 0 c,t_0>0 c , t 0 > 0 。對 n = b k n=b^k n = b k (k k k 為非負整數),令
T ( 1 ) = t 0 , T ( n ) = a T ( n / b ) + c n d ( n > 1 ) . T(1)=t_0,\qquad T(n)=aT(n/b)+cn^d\quad(n>1). T ( 1 ) = t 0 , T ( n ) = a T ( n / b ) + c n d ( n > 1 ) . 項 c n d cn^d c n d 是規模為 n n n 的節點上的非遞歸工作量,t 0 t_0 t 0 是葉的代價。記 p = log b a p=\log_b a p = log b a ,即 a = b p a=b^p a = b p 。漸近陳述指的是在參數固定的情況下,n n n 沿著 b b b 的冪趨於無窮。
定理
對每個 k ≥ 0 k\ge0 k ≥ 0 及 n = b k n=b^k n = b k ,
T ( n ) = t 0 a k + c n d ∑ i = 0 k − 1 ( a / b d ) i . T(n)=t_0a^k+cn^d\sum_{i=0}^{k-1}(a/b^d)^i. T ( n ) = t 0 a k + c n d i = 0 ∑ k − 1 ( a / b d ) i . 當 k = 0 k=0 k = 0 時和式為空,該恆等式即 T ( 1 ) = t 0 T(1)=t_0 T ( 1 ) = t 0 。
在上述假設下,
T ( n ) = { Θ ( n d ) , a < b d , Θ ( n d log n ) , a = b d , Θ ( n p ) , a > b d . T(n)=\begin{cases}
\Theta(n^d),&a<b^d,\\
\Theta(n^d\log n),&a=b^d,\\
\Theta(n^p),&a>b^d.
\end{cases} T ( n ) = ⎩ ⎨ ⎧ Θ ( n d ) , Θ ( n d log n ) , Θ ( n p ) , a < b d , a = b d , a > b d . 在漸近記號中,對數的底數無關宏旨。
證明思路
在深度 i < k i<k i < k 處有 a i a^i a i 個節點,每個節點的規模為 n / b i n/b^i n / b i 。它們的附加代價之和為 a i c ( n / b i ) d = c n d ( a / b d ) i a^ic(n/b^i)^d=cn^d(a/b^d)^i a i c ( n / b i ) d = c n d ( a / b d ) i 。遞歸在深度 k k k 處到達規模 1 1 1 ,共有 a k a^k a k 片葉,每片葉的代價為 t 0 t_0 t 0 。把各部分相加即得該恆等式。等價地,亦可對 k k k 作歸納:代入遞推式並平移和式的指標即可。
令 r = a / b d r=a/b^d r = a / b d 。若 r < 1 r<1 r < 1 ,則當 k ≥ 1 k\ge1 k ≥ 1 時,內部各層的和至少為 1 1 1 ,至多為 1 / ( 1 − r ) 1/(1-r) 1/ ( 1 − r ) ,因此它貢獻 Θ ( n d ) \Theta(n^d) Θ ( n d ) 。由於 p < d p<d p < d ,葉的代價 t 0 n p = O ( n d ) t_0n^p=O(n^d) t 0 n p = O ( n d ) 。若 r = 1 r=1 r = 1 ,每個內部層的代價都是 c n d cn^d c n d ,這樣的層共有 k = log b n k=\log_b n k = log b n 個。葉貢獻 t 0 n d t_0n^d t 0 n d ,所以總代價為 Θ ( n d log n ) \Theta(n^d\log n) Θ ( n d log n ) 。
若 r > 1 r>1 r > 1 ,幾何和為 ( r k − 1 ) / ( r − 1 ) = Θ ( r k ) (r^k-1)/(r-1)=\Theta(r^k) ( r k − 1 ) / ( r − 1 ) = Θ ( r k ) (r r r 固定)。此外 n d r k = n d ( a / b d ) k = a k = n p n^dr^k=n^d(a/b^d)^k=a^k=n^p n d r k = n d ( a / b d ) k = a k = n p 。內部工作量與葉的代價都是 O ( n p ) O(n^p) O ( n p ) ,而正的葉項本身已經是 Ω ( n p ) \Omega(n^p) Ω ( n p ) 。這就證明了最後一種情形。正的附加代價與正的基礎代價排除了互相抵消的可能,並提供了這裏用到的下界。
證明透視
比較整層的代價 關鍵的比值是 a / b d a/b^d a / b d :每深入一層,節點數乘以 a a a ,而每個節點上的工作量則縮小為原來的 1 / b d 1/b^d 1/ b d 。只計入其中一種變化,就會忽略兩者之間的競爭。
各項假設在特定的地方使用。固定的 a a a 、b b b 、d d d 使 r = a / b d r=a/b^d r = a / b d 為常數,因此幾何和是 Θ ( 1 ) \Theta(1) Θ ( 1 ) 、Θ ( k ) \Theta(k) Θ ( k ) 或 Θ ( r k ) \Theta(r^k) Θ ( r k ) ,其常數不依賴於 n n n 。正的 c c c 與 t 0 t_0 t 0 提供下界,因為沒有任何一項能抵消另一項。限制 n = b k n=b^k n = b k 使每一層的規模都是精確的。最後一種情形藉恆等式 n d r k = a k = n p n^dr^k=a^k=n^p n d r k = a k = n p 收尾,它把最大的一層代價與葉層等同起來。
例題詳解
對於 T ( n ) = 4 T ( n / 2 ) + n T(n)=4T(n/2)+n T ( n ) = 4 T ( n /2 ) + n (基礎代價為正常數),有 a = 4 a=4 a = 4 ,b = 2 b=2 b = 2 ,d = 1 d=1 d = 1 ,p = 2 p=2 p = 2 。因為 4 > 2 4>2 4 > 2 ,總代價為 Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) 。內部各層的代價隨深度逐層翻倍,葉貢獻 n 2 n^2 n 2 的量級。
對於 T ( n ) = 2 T ( n / 2 ) + n T(n)=2T(n/2)+n T ( n ) = 2 T ( n /2 ) + n ,每個內部層的代價都是 n n n 。這樣的層有 log 2 n \log_2 n log 2 n 個,葉有 n n n 片,所以總代價為 Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) ,而不僅僅是 Θ ( n ) \Theta(n) Θ ( n ) 。
對於 T ( n ) = 2 T ( n / 2 ) + n 2 T(n)=2T(n/2)+n^2 T ( n ) = 2 T ( n /2 ) + n 2 ,相鄰兩層代價之比為 1 / 2 1/2 1/2 。根貢獻 n 2 n^2 n 2 ,所有內部層合起來的貢獻小於 2 n 2 2n^2 2 n 2 ;葉貢獻 n n n 的量級。因此總代價為 Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) 。
常見錯誤
反例模式
一層的代價不是總代價 在 T ( n ) = 2 T ( n / 2 ) + n T(n)=2T(n/2)+n T ( n ) = 2 T ( n /2 ) + n 中,僅僅觀察到一層的代價為 n n n ,並不能證明總代價是線性的。代價相同的層共有對數個,由此產生了額外的因子 log n \log n log n 。
該定理不能直接用於 T ( n ) = T ( n − 1 ) + n T(n)=T(n-1)+n T ( n ) = T ( n − 1 ) + n (其子問題規模不是 n / b n/b n / b ),也不能直接用於 T ( n ) = 2 T ( n / 2 ) + n log n T(n)=2T(n/2)+n\log n T ( n ) = 2 T ( n /2 ) + n log n (其附加代價不是固定常數乘以 n d n^d n d )。這兩者都可以用其他求和方法分析;但不加證明地把它們代入這三種情形是無效的。
對 T ( n ) = 2 T ( n / 2 ) + n log 2 n T(n)=2T(n/2)+n\log_2 n T ( n ) = 2 T ( n /2 ) + n log 2 n ,也許會取 d = 1 d=1 d = 1 ,見到 a = b d a=b^d a = b d ,便答 Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) 。但附加代價並不是常數乘以冪。在深度 i i i 處,2 i 2^i 2 i 個節點各付 ( n / 2 i ) ( k − i ) (n/2^i)(k-i) ( n / 2 i ) ( k − i ) ,其中 k = log 2 n k=\log_2 n k = log 2 n ,所以內部代價為 n k ( k + 1 ) / 2 n\,k(k+1)/2 n k ( k + 1 ) /2 ,T ( n ) = Θ ( n log 2 n ) T(n)=\Theta(n\log^2 n) T ( n ) = Θ ( n log 2 n ) ;例如 T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 時,T ( 4 ) = 16 = 4 ⋅ 3 + 4 T(4)=16=4\cdot3+4 T ( 4 ) = 16 = 4 ⋅ 3 + 4 。
展開一棵小樹
透過寫出最初幾步代入,可以檢驗逐層公式。設 T ( n ) = 4 T ( n / 2 ) + n T(n)=4T(n/2)+n T ( n ) = 4 T ( n /2 ) + n ,T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 。則
T ( n ) = 4 ( 4 T ( n / 4 ) + n / 2 ) + n = 16 T ( n / 4 ) + 2 n + n . T(n)=4\bigl(4T(n/4)+n/2\bigr)+n=16T(n/4)+2n+n. T ( n ) = 4 ( 4 T ( n /4 ) + n /2 ) + n = 16 T ( n /4 ) + 2 n + n .
在最初三個內部層,代價依次為 n , 2 n , 4 n n,2n,4n n , 2 n , 4 n 。重數 4 i 4^i 4 i 與子問題規模 n / 2 i n/2^i n / 2 i 合起來給出每層代價 n 2 i n2^i n 2 i 。這與只沿著一條由根到葉的路徑觀察不同,因為那樣在每一層只看到眾多子問題中的一個。
對於 T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 與 T ( n ) = 4 T ( n / 2 ) + n T(n)=4T(n/2)+n T ( n ) = 4 T ( n /2 ) + n ,n = 8 n=8 n = 8 時各層代價為 8 8 8 、16 16 16 和 32 32 32 ,之後是 4 3 = 64 4^3=64 4 3 = 64 片代價為一的葉。因此 T ( 8 ) = 120 T(8)=120 T ( 8 ) = 120 。直接代入的結果一致:T ( 2 ) = 4 ⋅ 1 + 2 = 6 T(2)=4\cdot1+2=6 T ( 2 ) = 4 ⋅ 1 + 2 = 6 ,T ( 4 ) = 4 ⋅ 6 + 4 = 28 T(4)=4\cdot6+4=28 T ( 4 ) = 4 ⋅ 6 + 4 = 28 ,T ( 8 ) = 4 ⋅ 28 + 8 = 120 T(8)=4\cdot28+8=120 T ( 8 ) = 4 ⋅ 28 + 8 = 120 。葉的代價必須與基礎情形保持一致地計入。
葉的個數是 a k = n log b a a^k=n^{\log_b a} a k = n l o g b a ,一般並不等於 n n n 。在常見的 a = b a=b a = b 情形下它等於 n n n ,但當 a = 4 , b = 2 a=4,b=2 a = 4 , b = 2 時它是 n 2 n^2 n 2 。所有節點的總數是另一個幾何和,當 a > 1 a>1 a > 1 時為 1 + a + ⋯ + a k 1+a+\cdots+a^k 1 + a + ⋯ + a k ;由於節點的代價取決於其規模,僅憑它並不能確定執行時間。當 a = 1 a=1 a = 1 時,遞歸樹是一條含 k + 1 k+1 k + 1 個節點的單一路徑。
概念視角 代數
把層和看成一階線性遞推式 令 S ( k ) = T ( b k ) S(k)=T(b^k) S ( k ) = T ( b k ) 、β = b d \beta=b^d β = b d ,遞推式變成 S ( k ) = a S ( k − 1 ) + c β k S(k)=aS(k-1)+c\beta^k S ( k ) = a S ( k − 1 ) + c β k :齊次解為 a k a^k a k ,強迫項為 β k \beta^k β k 。若 β ≠ a \beta\ne a β = a ,則 S ( k ) = ( t 0 − B ) a k + B β k S(k)=(t_0-B)a^k+B\beta^k S ( k ) = ( t 0 − B ) a k + B β k ,其中 B = c β / ( β − a ) B=c\beta/(\beta-a) B = c β / ( β − a ) ,a a a 與 β \beta β 中較大者勝出:a > β a\gt\beta a > β 時由葉主導,a < β a\lt\beta a < β 時由根主導。若 β = a \beta=a β = a ,強迫項與齊次解共振,S ( k ) = a k ( t 0 + c k ) S(k)=a^k(t_0+ck) S ( k ) = a k ( t 0 + c k ) ,因子 k = log b n k=\log_b n k = log b n 就是多出來的對數。對 a = 4 , b = 2 , d = 1 a=4,b=2,d=1 a = 4 , b = 2 , d = 1 ,得 S ( k ) = 2 ⋅ 4 k − 2 k S(k)=2\cdot4^k-2^k S ( k ) = 2 ⋅ 4 k − 2 k ,S ( 3 ) = 120 S(3)=120 S ( 3 ) = 120 。
代入法證明及其局限
遞歸樹給出一個猜測的界,歸納法則可以驗證所提出的界。例如,在 2 2 2 的冪上令 T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 ,T ( n ) = 2 T ( n / 2 ) + n T(n)=2T(n/2)+n T ( n ) = 2 T ( n /2 ) + n 。精確公式為 T ( n ) = n log 2 n + n T(n)=n\log_2 n+n T ( n ) = n log 2 n + n 。它在 n = 1 n=1 n = 1 時成立。若它在 n / 2 n/2 n /2 處成立,則
2 ( ( n / 2 ) log 2 ( n / 2 ) + n / 2 ) + n = n log 2 n + n . 2\left((n/2)\log_2(n/2)+n/2\right)+n
=n\log_2 n+n. 2 ( ( n /2 ) log 2 ( n /2 ) + n /2 ) + n = n log 2 n + n .
因此該表達式在每個 2 2 2 的冪處都成立。這一證明同時檢驗了基礎情形與歸納步驟;它不斷言任何關於遞推式所聲明定義域之外的取值。
對於較寬鬆的漸近上界,歸納假設有時需要加上一個低階修正項才能閉合。盲目地在每個規模上假設 T ( n ) ≤ C n log n T(n)\le Cn\log n T ( n ) ≤ C n log n ,可能在基礎情形 n = 1 n=1 n = 1 處失敗,因為 log 1 = 0 \log1=0 log 1 = 0 而 T ( 1 ) > 0 T(1)>0 T ( 1 ) > 0 。此時可以改用足夠大的閾值,或加上一個線性項,或使用 log ( 2 n ) \log(2n) log ( 2 n ) ;每一種選擇都必須加以驗證。成功的歸納是對所述範圍和常數的證明,而不僅僅是由樹形圖提示的猜測。
精確恆等式也釐清了下界。根貢獻 c n d cn^d c n d ,葉貢獻 t 0 n p t_0n^p t 0 n p ,因此當各代價非負時,兩者各自都是下界。在各層相等的情形中,兩者單獨都不能給出額外的對數因子;把全部 k k k 個非負的層代價相加才可以。如果模型容許負的附加代價或互相抵消,這些下界論證就需要不同的假設。
一個單獨的取整例子
考慮對每個正整數定義的遞推式:U ( 1 ) = t 0 > 0 U(1)=t_0>0 U ( 1 ) = t 0 > 0 ,且
U ( n ) = U ( ⌊ n / 2 ⌋ ) + U ( ⌈ n / 2 ⌉ ) + c n ( n ≥ 2 ) , U(n)=U(\lfloor n/2\rfloor)+U(\lceil n/2\rceil)+cn\qquad(n\ge2), U ( n ) = U (⌊ n /2 ⌋) + U (⌈ n /2 ⌉) + c n ( n ≥ 2 ) ,
其中 c > 0 c>0 c > 0 。對任意 n n n ,該遞推式並不直接被精確的等規模定理所涵蓋,但它的樹可以獨立地加以估計。每個內部節點把其規模分成兩個正整數,其和等於父節點的規模。恰有 n n n 片規模為一的葉。深度 i < ⌊ log 2 n ⌋ i<\lfloor\log_2 n\rfloor i < ⌊ log 2 n ⌋ 處的所有節點規模至少為二,所以它們的規模之和為 n n n ,該層代價為 c n cn c n 。從根到葉的任何路徑所含的內部層都不超過 ⌈ log 2 n ⌉ \lceil\log_2 n\rceil ⌈ log 2 n ⌉ 個,而且任一層上各節點的規模之和至多為 n n n 。因此
c n ⌊ log 2 n ⌋ + t 0 n ≤ U ( n ) ≤ c n ⌈ log 2 n ⌉ + t 0 n , cn\lfloor\log_2 n\rfloor+t_0n
\le U(n)\le cn\lceil\log_2 n\rceil+t_0n, c n ⌊ log 2 n ⌋ + t 0 n ≤ U ( n ) ≤ c n ⌈ log 2 n ⌉ + t 0 n ,
這就證明了當 n ≥ 2 n\ge2 n ≥ 2 時 U ( n ) = Θ ( n log n ) U(n)=\Theta(n\log n) U ( n ) = Θ ( n log n ) 。
為了證明關於深度的陳述:經過 i i i 次均衡劃分後,每個現存子問題的規模要麼是 ⌊ n / 2 i ⌋ \lfloor n/2^i\rfloor ⌊ n / 2 i ⌋ ,要麼是 ⌈ n / 2 i ⌉ \lceil n/2^i\rceil ⌈ n / 2 i ⌉ 。這可由對「把每個規模劃分為其下取整一半與上取整一半」作歸納而得。在 i = ⌊ log 2 n ⌋ i=\lfloor\log_2 n\rfloor i = ⌊ log 2 n ⌋ 之前,較小的規模至少為二;到 i = ⌈ log 2 n ⌉ i=\lceil\log_2 n\rceil i = ⌈ log 2 n ⌉ 時,所有剩餘的規模都是一。這個論證處理了不均勻的最後一層,而不是假裝每個分支的深度都相同。
對於 n = 5 n=5 n = 5 ,第一次劃分得到規模 2 2 2 與 3 3 3 。下一次劃分,規模為二的節點產生規模 1 , 1 1,1 1 , 1 ,規模為三的節點產生規模 1 , 2 1,2 1 , 2 。其中一個規模為二的節點還需要再劃分一次。共有五片葉,而各內部層的規模之和依次為 5 5 5 、5 5 5 、2 2 2 。附加代價合共 12 c 12c 12 c ,葉的代價為 5 t 0 5t_0 5 t 0 ;取整的界包含了這個值。
從遞推式到算法結論
遞推式必須與所分析的算法相符。要數清楚進行了多少次遞歸調用、它們接收的規模是多少,以及這些調用之外還剩下多少工作。二分搜尋只對大約一半的輸入進行一次遞歸調用,而不是兩次;合併排序進行兩次調用,並帶有線性的合併工作。如果某些輸入令調用提早停止,則精確的遞推式可能只是最壞情形的界。只有在建立了遞推式與實作之間的聯繫之後,遞推式的數學解才是有用的。
附加代價是在選定模型下的代價。計算比較次數、算術運算次數、記憶體配置或位元運算,可能得到不同的遞推式。對於位元長度隨輸入增長的整數,常數時間算術的假設可能並不恰當。類似地,描述總工作量的遞推式並不自動描述記憶體峰值或並行執行時間:這些量合併遞歸調用的方式不同。
檢查邊界情形
當 a = 1 a=1 a = 1 且 d = 0 d=0 d = 0 時,樹是一條鏈,每個內部節點的附加代價為常數。它的長度是 log b n \log_b n log b n ,等層公式給出 Θ ( log n ) \Theta(\log n) Θ ( log n ) 。當 a = 1 a=1 a = 1 且 d > 0 d>0 d > 0 時,沿該鏈的附加代價按幾何級數遞減,由根主導。當 n = 1 n=1 n = 1 時,精確的和式沒有內部項,返回基礎代價。漸近表達式 n d log n n^d\log n n d log n 在 n = 1 n=1 n = 1 時不必為正;Θ \Theta Θ 描述的是足夠大的輸入,而不是每個規模下的精確公式。
如果所聲稱的遞推式中的常數依賴於 n n n ,則幾何比較可能改變。該定理把 a , b , c , d , t 0 a,b,c,d,t_0 a , b , c , d , t 0 固定,而輸入規模增長。例如,把像 log n \log n log n 這樣緩慢增長的因子當作常數,會改變附加代價,並可能丟掉整整一個對數因子。在應用有名稱的定理之前先寫下假設,往往是發現這類錯誤的最快方法。
定理之外的對數型附加代價
同樣的逐層方法可以求解一些不在三情形陳述之內的遞推式,但必須重新計算層和。設 T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 ,並在 2 2 2 的冪上令 T ( n ) = 2 T ( n / 2 ) + n log 2 n T(n)=2T(n/2)+n\log_2 n T ( n ) = 2 T ( n /2 ) + n log 2 n 。在深度 i < k = log 2 n i<k=\log_2 n i < k = log 2 n 處,2 i 2^i 2 i 個子問題的規模均為 n / 2 i n/2^i n / 2 i ,其對數為 k − i k-i k − i 。因此它們的附加代價之和為 n ( k − i ) n(k-i) n ( k − i ) 。內部代價為
n ∑ i = 0 k − 1 ( k − i ) = n k ( k + 1 ) 2 , n\sum_{i=0}^{k-1}(k-i)=n\frac{k(k+1)}2, n i = 0 ∑ k − 1 ( k − i ) = n 2 k ( k + 1 ) ,
n n n 片葉再加上 n n n 。故對足夠大的 2 2 2 的冪,T ( n ) = Θ ( n ( log n ) 2 ) T(n)=\Theta(n(\log n)^2) T ( n ) = Θ ( n ( log n ) 2 ) 。若把附加代價中的對數當作常數,就會錯誤地得到 Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) 。
這一推導是一次新的計算,而不是對所述冪型附加代價定理的應用。它說明了一種一般策略:寫出深度 i i i 處一個節點的工作量,乘以該深度的節點數,確定精確的終止深度,然後求和。如果這些量依賴於路徑,或輸入的規模不等,則可能不再存在單一的統一層公式。仍然可以像取整例子那樣對樹加以估計,但必須針對該遞推式證明所得的界。
即使實作在遞歸調用之間重用記憶體,遞歸樹的圖像描述的仍然是代價的算術總和。它並不意味著所有節點同時存在於記憶體中。反之,並行實作可能同時計算互相獨立的調用,因此其耗時取決於關鍵路徑與調度,而不是簡單地取決於總工作量。在解釋遞推式的解之前,應先說明該遞推式代表的是哪種資源。
最後的算術檢驗
對於由根主導的例子 T ( n ) = 2 T ( n / 2 ) + n 2 T(n)=2T(n/2)+n^2 T ( n ) = 2 T ( n /2 ) + n 2 (T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 ),精確的和式給出
T ( n ) = n + n 2 ∑ i = 0 k − 1 2 − i = n + 2 n 2 ( 1 − 2 − k ) = 2 n 2 − n . T(n)=n+n^2\sum_{i=0}^{k-1}2^{-i}=n+2n^2(1-2^{-k})=2n^2-n. T ( n ) = n + n 2 i = 0 ∑ k − 1 2 − i = n + 2 n 2 ( 1 − 2 − k ) = 2 n 2 − n .
該公式在 n = 1 n=1 n = 1 時成立,並且把它代入遞推式能在更大的 2 2 2 的冪處重現它。特別地,它的首項為正而且是二次的。在少數幾個小的輸入上做精確計算,可以發現放錯的葉項或錯誤的層比值,儘管有限次檢驗不能證明對所有輸入成立的漸近界。
總結
層比值 a / b d a/b^d a / b d 比較了節點數的增長與每個節點工作量的下降。遞減的幾何級數由根主導,各層代價相等則累積出一個對數因子,遞增的級數則由葉主導。在所述假設下,精確的逐層恆等式證明了這些結論。
練習
快速檢查
(對 2 2 2 的冪上的 T ( n ) = 8 T ( n / 2 ) + n 2 T(n)=8T(n/2)+n^2 T ( n ) = 8 T ( n /2 ) + n 2 (基礎代價為正常數)進行分類。)
解答 · 答案 這裏 a = 8 > b d = 4 a=8>b^d=4 a = 8 > b d = 4 ,且 p = 3 p=3 p = 3 ,所以 T ( n ) = Θ ( n 3 ) T(n)=\Theta(n^3) T ( n ) = Θ ( n 3 ) 。
快速檢查
(對 2 2 2 的冪上的 T ( n ) = T ( n / 2 ) + 1 T(n)=T(n/2)+1 T ( n ) = T ( n /2 ) + 1 進行分類。)
解答 · 答案 這裏 a = b d = 1 a=b^d=1 a = b d = 1 ,d = 0 d=0 d = 0 ,所以對足夠大的 2 2 2 的冪,T ( n ) = Θ ( log n ) T(n)=\Theta(\log n) T ( n ) = Θ ( log n ) 。
快速檢查
(對 3 3 3 的冪上的 T ( n ) = 3 T ( n / 3 ) + n 2 T(n)=3T(n/3)+n^2 T ( n ) = 3 T ( n /3 ) + n 2 進行分類。)
解答 · 答案 這裏 a = 3 < 9 = b d a=3<9=b^d a = 3 < 9 = b d ,所以 T ( n ) = Θ ( n 2 ) T(n)=\Theta(n^2) T ( n ) = Θ ( n 2 ) 。
快速檢查
(當 n = 8 n=8 n = 8 時,T ( n ) = 2 T ( n / 2 ) + n T(n)=2T(n/2)+n T ( n ) = 2 T ( n /2 ) + n 的遞歸樹有多少片葉?)
解答 · 答案 樹的深度為 log 2 8 = 3 \log_2 8=3 log 2 8 = 3 ,葉的個數為 2 3 = 8 2^3=8 2 3 = 8 。