Phân tích các chương trình đệ quy

Phương pháp truy hồi

Dùng đệ quy để thay thế bất kỳ T(m) với m < n vào phía phải của phương trình cho đến khi tất cả T(m) với m > 1 được thay thế bởi biểu thức của các T(1) hoặc T(0). Vì T(1) và T(0) luôn là hằng số nên chúng ta có công thức của T(n) chứa các số hạng chỉ liên quan đến n và các hằng số. Từ công thức đó ta suy ra T(n).

Ví dụ 1-12: Giải phương trình T(n) = C1 nêun=0T(n-1)+C2 nêun>0{ size 12{alignl { stack { left lbrace C rSub { size 8{1} } " nêu"~"n=0" {} # right none left lbrace T ( "n-1" ) +C rSub { size 8{2} } " nêu"~n>0 {} # right no } } lbrace } {}

Ta có T(n) = T(n-1) + C₂

T(n) = [T(n-2) + C₂] + C₂ = T(n-2) + 2C₂

T(n) = [T(n-3) + C₂] + 2C₂ = T(n-3) + 3C₂

……

T(n) = T(n-i) + iC₂

Quá trình trên kết thúc khi n - i = 0 hay i = n. Khi đó ta có

T(n) = T(0) + nC₂ = C₁ + n C₂ = O(n)

Ví dụ 1-13: Giải phương trình T(n) = {C1 nêu n =12T(n2)+ C2 n nêu n > 1 size 12{ left lbrace matrix { C rSub { size 8{1} } " nêu n "=1 {} ## "2T" ( { {n} over {2} } ) +" C" rSub { size 8{2} } " n nêu n ">" 1" } right none } {}

Ta có T(n)=2T(n2)+2C2n size 12{T ( n ) "=2T" ( { {n} over {2} } ) "+2C" rSub { size 8{2} } n} {}

T ( n ) = 2 [ 2T ( n 4 ) + C 2 n 2 ] + C 2 n = 4T ( n 4 ) + 2C 2 n size 12{T ( n ) ="2 " [ " 2T" ( { {n} over {4} } ) +" C" rSub { size 8{2} } { {n} over {2} } ] +C rSub { size 8{2} } "n "=" 4T" ( { {n} over {4} } ) +"2C" rSub { size 8{2} } n} {}

……….

Quá trình suy rộng sẽ kết thúc khi n2i size 12{ { {n} over {2 rSup { size 8{i} } } } } {} = 1 hay 2ⁱ = n và do đó i = logn. Khi đó ta có:

T(n) = nT(1) + lognC₂n = C₁n + C₂nlogn = O(nlogn).

Phương pháp đoán nghiệm

Ta đoán một nghiệm f(n) và dùng chứng minh quy nạp để chứng tỏ rằng T(n) ≤ f(n) với mọi n.

Thông thường f(n) là một trong các hàm quen thuộc như logn, n, nlogn, n2 size 12{n rSup { size 8{2} } } {}, n3 size 12{n rSup { size 8{3} } } {}, 2n size 12{2 rSup { size 8{n} } } {}, n!,nn size 12{n rSup { size 8{n} } } {}.

Ðôi khi chúng ta chỉ đoán dạng của f(n) trong đó có một vài tham số chưa xác định (chẳng hạn f(n) = an² với a chưa xác định) và trong quá trình chứng minh quy nạp ta sẽ suy diễn ra giá trị thích hợp của các tham số.

Ví dụ 1-12: Giải phương trình đệ quy T(n) = {C1 nêu n =12T(n2)+ C2 n nêu n > 1 size 12{ left lbrace matrix { C rSub { size 8{1} } " nêu n "=1 {} ## "2T" ( { {n} over {2} } ) +" C" rSub { size 8{2} } " n nêu n ">" 1" } right none } {}

Giả sử chúng ta đoán f(n) = anlogn. Với n = 1 ta thấy rằng cách đoán như vậy không được bởi vì anlogn có giá trị 0 không phụ thuộc vào giá trị của a. Vì thế ta thử tiếp theo f(n) = anlogn + b.

Với n = 1 ta có, T(1) = C₁ và f(1) = b, muốn T(1) ≤ f(1) thì b ≥ C₁ (*)

Giả sử rằng T(k) ≤ f(k), tức là T(k) ≤ aklogk + b với mọi k < n (giả thiết quy nạp). Ta phải chứng minh T(n) ≤ anlogn + b với mọi n.

Giả sử n ≥ 2, từ phương trình đã cho ta có T(n) = 2T( n2 size 12{ { {n} over {2} } } {}) + C₂n

Áp dụng giả thiết quy nạp với k = n2 size 12{ { {n} over {2} } } {} < n ta có:

T(n) = 2T( n2 size 12{ { {n} over {2} } } {}) + C₂n ≤ 2[a n2 size 12{ { {n} over {2} } } {}log n2 size 12{ { {n} over {2} } } {} + b] + C₂n

T(n) ≤ (anlogn - an + 2b) + C₂n

T(n) ≤ (anlogn + b) + [b + (C₂ - a)n] . Nếu lấy a ≥ C₂ + b (**) ta được

T(n) ≤ (anlogn + b) + [b +(C₂ - C₂ - b )n ]

T(n) ≤ (anlogn + b) + (1-n) b

T(n) ≤ anlogn + b = f(n). (do b>0 và 1-n<0)

Nếu ta lấy a và b sao cho cả (*) và (**) đều thoả mãn thì T(n) ≤ an logn + b với mọi n.

{b≥C1a≥C2+b size 12{ left lbrace matrix { b >= C rSub { size 8{1} } {} ## a >= C rSub { size 8{2} } +b } right none } {}Ta phải giải hệ Ðể đơn giản, ta giải hệ {b=C1a=C2+b size 12{ left lbrace matrix { "b=C" rSub { size 8{1} } {} ## "a=C" rSub { size 8{2} } "+b" } right none } {}

Dễ dàng ta có b = C₁ và a = C₁ +C₂ ta được T(n) ≤ (C₁ + C₂)nlogn +C₁ với mọi n.

Hay nói cách khác T(n) là O(nlogn).

Lời giải tổng quát cho một lớp các phương trình đệ quy

Khi thiết kế các giải thuật, người ta thường vận dụng phương pháp chia để trị mà ta sẽ bàn chi tiết hơn trong chương 3. Ở đây chi trình bày tóm tắt phương pháp như sau:

Ðể giải một bài toán kích thước n, ta chia bài toán đã cho thành a bài toán con, mỗi bài toán con có kích thước nb size 12{ { {n} over {b} } } {}. Giải các bài toán con này và tổng hợp kết quả lại để được kết quả của bài toán đã cho. Với các bài toán con chúng ta cũng sẽ áp dụng phương pháp đó để tiếp tục chia nhỏ ra nữa cho đến các bài toán con kích thước 1. Kĩ thuật này sẽ dẫn chúng ta đến một giải thuật đệ quy.

Giả thiết rằng mỗi bài toán con kích thước 1 lấy một đơn vị thời gian và thời gian để chia bài toán kích thước n thành các bài toán con kích thước nb size 12{ { {n} over {b} } } {} và tổng hợp kết quả từ các bài toán con để được lời giải của bài toán ban đầu là d(n). (Chẳng hạn đối với ví dụ MergeSort, chúng ta có a = b = 2, và d(n) = C₂n. Xem C₁ là một đơn vị).

Tất cả các giải thuật đệ quy như trên đều có thể thành lập một phương trinh đệ quy tổng quát, chung cho lớp các bài toán ấy.

Nếu gọi T(n) là thời gian để giải bài toán kích thước n thì T( nb size 12{ { {n} over {b} } } {}) là thời gian để giải bài toán con kích thước nb size 12{ { {n} over {b} } } {}. Khi n = 1 theo giả thiết trên thì thời gian giải bài toán kích thước 1 là 1 đơn vị, tức là T(1) = 1. Khi n lớn hơn 1, ta phải giải đệ quy a bài toán con kích thước nb size 12{ { {n} over {b} } } {}, mỗi bài toán con tốn T( nb size 12{ { {n} over {b} } } {}) nên thời gian cho a lời giải đệ quy này là aT( nb size 12{ { {n} over {b} } } {}). Ngoài ra ta còn phải tốn thời gian để phân chia bài toán và tổng hợp các kết quả, thời gian này theo giả thiết trên là d(n).

Vậy ta có phương trình đệ quy:

T(n) = {C1 nêu n =12T(n2)+ C2 n nêu n > 1 size 12{ left lbrace matrix { C rSub { size 8{1} } " nêu n "=1 {} ## "2T" ( { {n} over {2} } ) +" C" rSub { size 8{2} } " n nêu n ">" 1" } right none } {}

Ta sử dụng phương pháp truy hồi để giải phương trình này. Khi n > 1 ta có

T(n) = aT( nb size 12{ { {n} over {b} } } {}) + d(n)

T(n)= a[aT(nb2) + d(nb)]+d(n)=a2T(nb2)+ad(nb)+d(n) size 12{a [ "aT" ( left ( { {n} over {b rSup { size 8{2} } } } ) " + d" ( { {n} over {b} } ) right ) ] "+d" ( n ) "=a" rSup { size 8{2} } T ( left ( { {n} over {b rSup { size 8{2} } } } right ) ) "+ad" ( left ( { {n} over {b} } ) right )"+d" ( n ) } {}

T(n)= a2[a T(nb3)+d(nb2)]+ad(nb)+d(n)=a3T(nb3)+a2d(nb2)+ad(nb)+d(n) size 12{a rSup { size 8{2} } [ "a T" ( { {n} over {b rSup { size 8{3} } } } ) +d left ( ( { {n} over {b rSup { size 8{2} } } } ) right ) ] +"ad" left ( ( { {n} over {b} } ) right )+d ( n ) =a rSup { size 8{3} } T left ( ( { {n} over {b rSup { size 8{3} } } } ) right )+a rSup { size 8{2} } d left ( ( { {n} over {b rSup { size 8{2} } } } ) right )+"ad" left ( ( { {n} over {b} } ) right )+d ( n ) } {} = ........

= aiT(nbi)+∑j=0i-1ajd(abj) size 12{a rSup { size 8{i} } T ( left ( { {n} over {b rSup { size 8{i} } } } ) right )+ Sum cSub { size 8{j=0} } cSup { size 8{"i-1"} } {a rSup { size 8{j} } d ( left ( { {a} over {b rSup { size 8{j} } } } ) right )} } {}

Giả sử n = b^k, quá trình suy rộng trên sẽ kết thúc khi i = k.

Khi đó ta được T( nbk size 12{ { {n} over {b rSup { size 8{k} } } } } {}) = T(1) = 1. Thay vào trên ta có:

T(n) = ak+∑j=0k-1ajdbk-j size 12{a rSup { size 8{k} } + Sum cSub { size 8{j=0} } cSup { size 8{"k-1"} } {a rSup { size 8{j} } d left (b rSup { size 8{"k-j"} } right )} } {} (I.2)