Thiết kế và đánh giá thuật toán

Do đó, T(n) = O(n).

Ví dụ 1.9.

T(n) =

Giải phương trình truy hồi sau:

Ta có với n>1:

T(n) = 2T( n )+c2n

n n

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

c1 nếu n=1

2T( n )+c2n nếu n>1

n 2 n

= 2(2T( )+c2 ) + c2n = 4 T( ) + 2c2n = 2 T( ) + 2c2n

4 2 4 2 2

n n n 3 n

= 4( 2T( )+c2 ) + 2c2n = 8T( ) + 3c2n = 2 T( ) + 3c2n

8 4 8 23

.....

= 2iT(

n ) + ic2n

Quá trình sẽ dừng khi:

n =1

 n =2i

 i = log2n Khi đó: T(n) = nT(1) + c2nlog2n

= nc1 + c2nlog2n Và T(n) = O(nlog2n)

* 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ư log2n, n, nlog2n, n2, n3, 2n, n!, nn.

Ðô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) = an2 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.10. Giải phương trình truy hồi sau:

T(n)=

c1 nếu n=1

2T( n )+c2n nếu n>1

Giả sử chúng ta đoán f(n) = anlog2n. Với n = 1 ta thấy rằng việc đoán như vậy không được bởi vì anlog2n 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) = anlog2n + b.

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

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

Giả sử n ≥ 2, từ phương trình đã cho ta có T(n) = 2T( n )+ c2n

Áp dụng giả thiết quy nạp với k = n ta có

T(n) = 2T( n

)+ c2n  2(a n

log2 n

+ b) +c2n

T(n) ≤ (anlog2n - an + 2b) + c2n

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

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

T(n) ≤ anlog2n + 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 Tức là:

b  c1

a  c2 + b thì T(n) ≤ anlog2n + b với mọi n

Như vậy với b  c1 và a  c1 + c2 thì ta sẽ có T(n) ≤ (c1 + c2)nlog2n +c1 với mọi n. Hay nói cách khác T(n) là O(nlog2n).

* Phương pháp dùng phương trình đặc trưng với phương trình truy hồi tuyến tính thuần nhất hệ số hằng

Phương trình truy hồi (công thức truy hồi) tuyến tính thuần nhất bậc k với hệ số hằng số có dạng:

an = c1an-1 + c2an-2 + ...+ ckan-k trong đó c1, c2, ..., ck là các số thực, ck  0

Nếu cho trước k điều kiện ban đầu a0 = c0, a1 = c1, ..., ak-1 = ck-1 ,thì theo qui nạp toán học, dãy số thoả mãn phương trình truy hồi nêu trong định nghĩa sẽ được xác định duy nhất.

Phương pháp cơ bản để giải phương trình truy hồi tuyến tính thuần nhất là tìm nghiệm dưới dạng an = rn, trong đó r là hằng số. Ta có an = rn là nghiệm của

phương trình truy hồi an = c1an-1 + c2an-2 + ...+ ckan-k khi và chỉ khi:

rn = c1rn-1 + c2rn-2 + ... + ckrn-k

Hay rn - c1rn-1 - c2rn-2 - ... - ckrn-k = 0

Vậy, dãy {an} với an = rn là nghiệm khi và chỉ khi r là nghiệm của phương trình đại số trên. Phương trình này được gọi là phương trình đặc trưng của công thức truy hồi và nghiệm của nó được gọi là nghiệm đặc trưng của phương trình truy hồi. Các nghiệm đặc trưng sẽ dùng cho công thức tường minh của tất cả các nghiệm của phương trình truy hồi.

Đối với phương trình truy hồi tuyến tính thuần nhất bậc 2 khi phương trình đặc trưng có hai nghiệm phân biệt r1, r2. Khi đó dãy số {an} là nghiệm của công thức truy hồi an = c1an-1 + c2an-2 khi và chỉ khi

an = 1r1n + 2r2n

với n= 0, 1, 2,... ,trong đó 1, 2 là các hằng số.

Ngược lại, giả sử {an} là một nghiệm bất kỳ của phương trình truy hồi, ta sẽ chọn 1 và 2 sao cho dãy {an} với an = a1r1n + a2r2n thoả mãn các điều kiện đầu a0

= c0, a1 = c1. Thật vậy, đặt:

a0 = c0 = 1 + 2

a1 = c1 = a1r1 + a2r2

Từ phương trình đầu ta được 2 = c0 - 1. Thay vào phương trình sau ta

được:

c1 = a1r1 + (c0 - 1)r2 = a1(r1 - r2) + c0r2

Suy ra 

C C r

1 0 2

r1 r2

và 

C 

C C r

C 1 0 2

= C0 r1 C1

2 0 1 0

r1 r2

Vậy khi chọn các giá trị a1 và a2 này thì dãy {an} với an = a1r1n + a2r2n thoả mãn các điều kiện đầu. Vì phương trình truy hồi và các điều kiện đầu xác định duy nhất, nên an = a1r1n + a2r2n .

Ví dụ 1.11.

Giả sử rằng các con thỏ không bao giờ chết. Biết rằng một cặp thỏ sau 2 tháng tính từ khi ra đời sẽ sinh ra một cặp thỏ mới và sau đó cứ mỗi tháng lại sinh ra một cặp thỏ mới. Hỏi nếu tháng đầu có một cặp thỏ thì đến tháng thứ n sẽ có bao

nhiêu cặp thỏ?

Giải:

Gọi số cặp thỏ có ở tháng thứ n là Fn thì theo giả thiết F1 = F2 = 1. Với n>2 ta nhận thấy rằng: Số cặp thỏ có ở tháng thứ n sẽ là số cặp thỏ có ở tháng thứ n-1 (là Fn-1) cộng với số cặp thỏ mới được sinh ra ở tháng thứ n - chính là số cặp thỏ có ở tháng thứ n-2 (là Fn-2). Tức là:

Fn = Fn-1 + Fn-2 với n>2.

Vì vậy có thể tính Fn theo hệ thức truy hồi sau:

Fn =

1 nếu n 2

Fn-1+ Fn-2 nếu n >2

Dãy số thể hiện Fn với các giá trị của n được gọi là dãy số Fibonacci.

Từ hệ thức truy hồi trên ta dễ dàng có được giải thuật sau để tính số cặp thỏ có ở tháng thứ n.

Fibo(n)

{

if(n<=2) return(1); else

return(Fibo(n-1) + Fibo(n-2));

}

Ta đánh giá độ phức tạp tính toán của giải thuật. Gọi T(n) là thời gian thực hiện giải thuật thì ta có phương trình truy hồi sau:

C1 nếu n  2

T(n) =

T(n-1)+T(n-2) nếu n >2

Giải phương trình đặc trưng r2- r- 1 = 0 ta thu được hai nghiệm:

1  5

r1 2

1  5

r 

2 2

Khi đó ta có T(n) = 1r1n + 2r2n (*) trong đó 1, 2 là các hằng số cần xác định từ các giá trị ban đầu T(1) và T(2). Thay T(1) và T(1) vào (*) và giải ra ta được

1 

Khi đó ta có:

2 

5 

1 



5 n



1 

5 n 



Hay:

T( n )









2 2 

T(n) = O ( 1 

5 )n

Như vậy độ phức tạp tính toán của giải thuật là cấp hàm mũ.

Trong các ví dụ sau tài liệu chỉ đưa ra các cách giải phương trình truy hồi (hệ thức truy hồi, công thức truy hồi) từ đó người đọc có thể dễ dàng vận dụng để xác định độ phức tạp tính toán của giải thuật tương ứng.

Ví dụ 1.12.

Tìm nghiệm của công thức truy hồi an = an-1 + 2an-2, với a0 = 2, a1 = 7

Giải: Phương trình đặc trưng của công thức truy hồi này có dạng r2 - r -2 = 0. Nghiệm của nó là r=2 và r=-1. Theo định lý 1 dãy {an} là nghiệm của công thức truy hồi khi và chỉ khi an = 12n + 2(-1)n với các hằng số a1 và a2 nào đó. Từ các điều kiện đầu ta suy ra:

a0 = 2 = 1 + 2

a1 = 7 = a12 + a2(-1)

Giải ra ta được 1 = 3 và 2 = -1. Vậy nghiệm của công thức truy hồi với điều kiện đầu là dãy {an} với an = 3.2n - (-1)n

Trong trường hợp phương trình đặc trưng của công thức truy hồi tuyến tính thuần nhất bậc 2 có nghiệm đặc trưng là nghiệm bội (chỉ có một nghiệm r0) khi đó dãy số { an} là nghiệm của công thức truy hồi an = c1an-1 + c2an-2 khi và chỉ khi

an = 1r0n + 2n r0n với n= 0, 1, 2,..trong đó 1, 2 là các hằng số.

Ví dụ 1.13.

Tìm nghiệm của hệ thức truy hồi an = 6an-1- 9an-2 với các điều kiện ban đầu a0= 1 và a1 =6.

Giải: Phương trình đặc trưng r2- 6r+ 9 = 0 có nghiệm kép r = 3. Do đó nghiệm của hệ thức truy hồi có dạng: an = 1 3n + 2n3n. Từ điều kiện đầu a0= 1 và

a1 =6 suy ra 1 = 1 và 2 = 1. Do vậy nghiệm của hệ thức truy hồi và các điều kiện

ban đầu đã cho là: an = 3n + n3n

Tổng quát hóa kết quả trên cho trường hợp hệ thức truy hồi tuyến tính thuần

nhất hệ số hằng bậc k > 2. Giả sử phương trình đặc trưng rk- c1rk-1- c2rk-2-...- ck = 0 có k nghiệm phân biệt r1, r2,..., rk. Khi đó dãy số {an} là nghiệm của hệ thức truy hồi an = c1an-1 + c2an-2+...+ ckan-k khi và chỉ khi

an = 1r1n + 2r2n+...+ krkn

với n= 0, 1, 2,... trong đó 1, 2 ,.., k là các hằng số.

Ví dụ 1.14.

Tìm nghiệm của hệ thức an = 6an-1- 11an-2 + 6an-3 với điều kiện đầu a0 = 2, a1

= 5, a2 = 15.

Giải: Phương trình đặc trưng r3- 6r2 + 11r- 6 = 0

có 3 ngiệm r1 = 1, r2 = 2, r3 = 3. Vì vậy, nghiệm có dạng an = 11n + 22n+ 33n.

Sử dụng các điều kiện đầu ta có 1=1, 2 =-1, 3 = 2. Vậy nghiệm của hệ thức đã cho là an = 1- 2n+ 2.3n.

* Phương trình truy hồi có dạng:

T(n) =

aT(n/b)+d(n)

nếu n =1

nếu n >1

(1)

Để xác định độ phức tạp tính toán của thuật toán theo phương trình truy hồi trên ta thực hiên như sau:

Chia bài toán kích thước n thành a bài toán con mỗi bài toán con có kích thước n/b. Giải các bài toán con này và tổng hợp các kết quả ta được lời giải của bài toán ban đầu. Với các bài toán con ta cũng áp dụng kỹ thuật này thì đến một lúc bài toán con sẽ có kích thước là 1. Kỹ thuật này sẽ dẫn ta đến một giải thuật đệ quy.

Gọi thời gian để giải quyết bài toán đã cho kích thước n là T(n), thời gian để giải quyết bài toán con kích thước n/b là T(n/b), thời gian để giải quyết bài toán con kích thước 1 là 1, thời gian để phân tích bài toán thành các bài toán con kích thước n/b và tổng hợp kết quả là d(n) thì ta sẽ có phương trình (1).

Với phương trình (1) khi n>1 ta có:

T(n) = aT(

) + d(n)

= a(aT( n

b 2

) + d( n

)) + d(n)

= a2T( n

b 2

) + d(n) + ad( n )

= a2(aT(

n ) + d( n

b3 b 2

))+ d(n) + ad( n )

= a3T( n

n 2 n )

....

b3 ) + d(n) + ad( b )+ a d( b 2

=aiT( n

n 2 n

i-1 n

bi ) + d(n) + ad( b )+ a d( b 2

) +...+a

d( )

bi1

i1 n

i a j d( )

= a T( ) +

j

j 0

Giả sử n = bk khi đó ta sẽ có:

k 1 n

k a j d( )

T(n) = a T(

b k

) + j

j0

= akT(1) +

k 1 n



a j d( )

j0 b j

= ak +

k 1 n



a j d(

j0 b j

) = ak +

k 1



a j d( bk j )

j 0

(2)

Trong (1) hàm d(n) được gọi là hàm tiến triển.

Trong (2) hàm ak được gọi là nghiệm thuần nhất. Nghiệm thuần nhất biểu diễn thời gian để giải các bài toán con.Ta có:

bk = n k = logbn

Do đó ak =

alogbn =

alogblogan =

nlogba

Trong (2) hàm

k 1



a j d( bk j )

j 0

được gọi là nghiệm riêng. Nghiệm riêng biểu

diễn thời gian để tạo các bài toán con và tổng hợp kết quả. Dễ thấy rằng nghiệm riêng phụ thuộc vào hàm tiến triển, số lượng và kích thước các bài toán con.

Theo qui tắc tổng trong (2) ta nhận thấy trong hai nghiệm: nghiệm riêng và nghiệm thuần nhất nghiệm nào lớn hơn thì đó là nghiệm của phương trình truy hồi. Việc xác định nghiệm riêng nói chung là phức tạp, ở đây ta chỉ quan tâm đến một lớp các phương trình dạng (1) mà ở đó hàm tiến triển có những dạng mà từ đó ta có thể dễ dàng tìm được nghiệm riêng.

Hàm nhân: Một hàm f(n) được gọi là hàm nhân nếu với mọi n, m nguyên dương ta đều có f(n.m)=f(n).f(m)

Ví dụ 1.15.

Hàm f(n) = nk là một hàm nhân vì:

f(n.m) = (nm)k = nk.mk = f(n).f(m)

+ Tìm nghiệm của (1) trong trường hợp d(n) là hàm nhân. Nếu d(n) là hàm nhân thì khi đó ta có:

k 1

a j d( bk j )

k 1

a j d k j ( b )

k 1

j 0

k j

( a

k d( b )

)k 1



j 0

= 

j0

= d ( b )( d( b ) )

d ( b )

a1 d( b )

Như vậy nghiệm riêng của (2) sẽ là:

a k d k ( b )

(3)

a 1 d( b )

Khi đó xảy ra các trường hợp sau:

1- Nếu a > d(b) thì trong (3) ta có ak > dk(b), theo quy tắc tổng độ phức tạp của nghiệm riêng là O(ak) bằng độ phức tập của nghiệm thuần nhất và đều bằng

O( nlogba), tức la T(n) =O( nlogba)