Ví dụ 1.16.
Giải phương trình truy hồi sau:
T(n) =
1 nếu n =1
4T(n/2)+ n nếu n >1
Giải:
Phương trình có dạng (1) với a=4, b=2 và d(n) = n. Vì d(n) = n nên dễ thấy
rằng d(n) là hàm nhân và d(b) = d(2) =2< a.
Có thể bạn quan tâm!
-
Thiết kế và đánh giá thuật toán - 2 -
Ðộ Phức Tạp Của Chương Trình Có Gọi Chương Trình Con Không Đệ Qui -
Thiết kế và đánh giá thuật toán - 4 -
Một Số Thuật Toán Sắp Xếp Bài Toán : -
Sắp Xếp Dãy A Theo Thứ Tự Tăng Dần Lúc Này A Đã Được Sắp Thứ Tự. -
Thiết kế và đánh giá thuật toán - 8
Xem toàn bộ 205 trang tài liệu này.
2
Vậy T(n) = O( nlog24) = O( nlog22) = O(n2)
2- Nếu a < d(b) thì ak < dk(b) thì theo quy tắc tổng độ phức tạp nghiệm riêng là O(dk(b)) lớn hơn của nghiệm thuần nhất là O(ak). Do đó:
T(n) = O(dk(b))
Ta có: d k( b ) [ d( b )] logbn[ d( b )]logbd ( b )logd ( b ) nnlogbd ( b )
Vậy T(n) =O(n logb d( b ))
Ví dụ 1.17.
Giải phương trình truy hồi sau:
T(n) =
1
4T(n/2)+ n3
nếu n =1
nếu n >1
Giải:
Phương trình có dạng (1) với a=4, b=2 và d(n) = n3. Vì d(n) = n3 nên d(n) là
hàm nhân và d(b) = d(2) =23 > a.
3
Vậy T(n) = O( nlog22) = O(n3)
3- Nếu a = d(b) thì (3) không xác định, trong trường hợp này ta phải tính trực tiếp nghiệm riêng. Ta có:
a
k 1
k j
k 1
k k
j 0
d ( b )( d( b ) )
a 1 a k
a
j 0
Do bk = n k = logbn và ak =
alogbn =
alogblogan =
nlogba
Nên nghiệm riêng sẽ là:
nlogbalogbn
Nghiệm riêng lớn hơn nghiệm thuần nhất ( nlogbalogbn > Vậy ta có: T(n) = O( nlogbalogbn)
Ví dụ 1.18.
alogbn )
Giải:
Giải phương trình truy hồi sau:
T(n) =
1 nếu n =1
2T(n/2)+ n nếu n >1
Phương trình có dạng (1) với a=2, b=2 và d(n) = n. Vì d(n) = n nên d(n) là
hàm nhân và d(b) = d(2) =2 = a.
Vậy T(n) = O( nlog22log2n) = O(nlog2n)
+ Tìm nghiệm của (1) trong trường hợp d(n) không phải là một hàm nhân. Trong trường hợp này ta phải tính trực tiếp nghiệm riêng rồi lấy nghiệm lớn hơn trong hai nghiệm: nghiệm riêng và nghiệm thuần nhất làm nghiệm của (1).
Ví dụ 1.19.
Giải phương trình truy hồi sau:
T(n) =
1 nếu n =1
2T(n/2)+ nlog2n nếu n >1
Giải:
Phương trình có dạng (1) với a=2, b=2 và d(n) = nlog2n. Dễ thấy rằng d(n)
không phải là hàm nhân nên ta trực tiếp tìm nghiệm riêng như sau:
k 1 k 1
2
a j d( bk j ) 2 j 2k j log
2k j
k 1
k( k 1 )
2k ( k j ) 2k
2
j0
j0
j0
Ta có O(2k k( k 1 ) ) = O(2kk2) = O(nlog22n) ( vì k = logbn = log2n)
2
Nghiệm thuần nhất 2k = n
Nghiệm riêng lớn hơn nghiệm thuần nhất nên ta có:
T(n) = O(nlog22n)
BÀI TẬP CHƯƠNG 1
1. Xác định độ phức tạp tính toán của giải thuật sau: sapxep1(a,n)
{
for(i=1;i<=n-1;i++)
{ m=i; for(j=i+1;j<=n;J++)
if(a[j]<a[m]) m=j; if(m!=i)
{
tg=a[i]; a[i]=a[m]; a[m]=tg;
}
}
}
2. Xác định độ phức tạp tính toán của giải thuật sau: Tim_kiem(a,n,x)
{
i=1;
while ((i<=n)&&(a[i]!=x)) i++;
if(i>n) return(0) else
return(i);
}
3. Xác định độ phức tạp tính toán của đoạn chương trình sau: for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
c[i,j] := 0;
for(k=1;k<=n;k++)
c[i,j] := c[i,j] + a[i,k] * b[k,j];
}
4. Xác định độ phức tạp tính toán của giải thuật sau: sap_xep(a,n)
{
for(i=2;i<=n;i++)
{
x=a[i]; j=i-1;
while((j>=1)&&(x<k[j]))
{
a[j+1]=a[j]; j=j-1;
}
a[j+1]=x;
}
}
5. Xác định độ phức tạp tính toán của giải thuật sắp xếp kiểu vun đống Hướng dẫn:
Dãy khoá K gồm n khoá. Để sắp xếp dãy khoá theo thứ tự tăng dần theo kiểu vun đống ta xây dựng các hàm ADJUST và HEAP_SORT.
Hàm ADJUST(i,n) thực hiện việc chỉnh lý một cây nhị phân hoàn chỉnh với gốc i để cây trở thành đống. Cây con trái và cây con phải của i, tức là cây với gốc là 2i và 2i+1 đã thoả mãn điều kiện của đống. Không có nút nào ứng với chỉ số lớn hơn n.
ADJUST được gọi trong HEAP_SORT. ADJUST(i,n)
{
// Khởi đầu key=k[i]; j=2*i;
// Chọn con ứng với khoá lớn nhất trong hai con của i while(j<=n)
{
if((j<n)&&(k[j]<k[j+1])) j=j+1;
// So sánh khoá cha với khoá con lớn nhất if (key>k[j])
{
k[[j/2]]=key; return;
}
k[[j/2]]=k[j]; j=2*j;
}
k[[j/2]]=key; return;
}
Ta coi phép toán tích cực là phép so sánh (j<n)&&(k[j]<k[j+1]) có thời gian
là O(1). Thuật toán trên chỉ duyệt trên một nhánh (nhánh có khoá lớn hơn) của cây nhị phân. Do vậy sau mỗi lần lặp thì số nút chỉ còn lại một nửa. Nếu số nút lúc đầu là n thì trong trường hợp xấu nhất thì lệnh lặp while phải thực hiện i lần sao cho 2i = n tức là i = log2n. Mỗi lần lặp phép toán tích cực được thực hiện một lần, do đó độ phức tạp tính toán của thuật toán là O(log2n).
HEAP_SORT(k,n)
{
//Tạo đống ban đầu for(i=[n/2];i>=1;i--)
ADJUST(i,n);
// Sắp xếp
for(i=n-1;i>=1;i--)
{
x=k[1]; k[1]=k[i+1];
k[i+1]=x;
}
}
Trong thuật toán này vòng lặp for(i=[n/2];i>=1;i--) thực hiện lặp n/2 lần, mỗi lần lặp gọi ADJUST(i,n). Do vậy độ phức tạp tính toán của HEAP_SORT là O(nlog2n).
6. Giải các phương trình truy hồi sau:
T(n) =
T(n) =
1
3T(n/2)+ n
1
3T(n/2)+ n
2
nếu n =1
nếu n >1
nếu n =1
nếu n >1
a)
b)
T(n) =
1
c) 8T(n/2)+ n3
nếu n =1
nếu n >1
7. Giải các phương trình truy hồi sau:
a) T(1) = 2 và T(n) = 2T(n-1) + 1 với n > 1
b) T(1) = 3, T(2)=6 và T(n) = T(n-1) + 6T(n-2) với n > 2
8. Cho tổng
S 1 1 1 ... 1
với n nguyên dương
2 3 n
Viết một giải thuật không đệ quy và một giải thuật đệ quy tính tổng trên và đánh giá độ phức tạp tính toán của các giải thuật đó.
Hướng dẫn:
Thuật toán đệ quy:
tong(n)
{
if(n==1) return(1);
else return(tong(n-1)+1/n);
}
Đánh giá độ phức tạp:
- Xây dựng phương trình truy hồi
c1 nếu n=1
T(n)=
T(n-1) + c2 nếu n>1
- Giải phương trình truy hồi T(n) = T(n-1) + c2
= T(n-2) + 2c2
....
= T(1) + (n-1)c2
- Độ phức tạp tính toán của giải thuật: T(n) =O(n).
9. Cho dãy a gồm n số nguyên đã được sắp xếp theo thứ tự tăng dần, các phần tử của dãy được đánh chỉ số từ 1 đến n. Xác định độ phức tạp tính toán của các giải thuật sau:
a. Giải thuật tìm kiếm nhị phân TKNP(a,n,x)
{
l=1;
r=n; while(l<=r)
{
m=[(l+r)/2];
if(x<a[m]) r=m-1; else
if(x>a[m]) l=m+1; else return(m)
return(0);
}
b. Giải thuật tìm kiếm nhị phân đệ quy TKNP(l,r,a,x)
{
if(l>r) loc=0; else
{
m=[(l+r)/2];
if(x<a[m]) loc=TKNP(l,m-1,a,x); else
if(x>a[m]) loc=TKNP(m+1,r,a,x) else
loc=m;
return(loc);
}
Hướng dẫn ý b.
- Xây dựng phương trình truy hồi:
c1 nếu n=1
T(n)=
Với n>1 ta có:
T( n
2
n
)+c2 nếu n>1
T(n) = T(
2
= T( n
4
n
)+ c2
)+ 2c2
= T( )+ 3c2
8
....
= T(
n )+ ic2
2i
Dừng khi
n =1 n=2i i=log2n
2i
Do đó T(n) = T(1) + c2log2n
= c1 + c2log2n
= O(log2n)