Giải bài tập phân tích và thiết kế thuật toán năm 2024

0% found this document useful (0 votes)

9 views

6 pages

Original Title

BÀI TẬP CHƯƠNG 2_PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN

Copyright

© © All Rights Reserved

Available Formats

DOCX, PDF, TXT or read online from Scribd

Share this document

Did you find this document useful?

0% found this document useful (0 votes)

9 views6 pages

BÀI TẬP CHƯƠNG 2 - PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN

Jump to Page

You are on page 1of 6

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

• 1. tích giải thuật Phạm Nguyên Khang, Đỗ Thanh Nghị Khoa CNTT – Đại học Cần Thơ {pnkhang,dtnghi}@cit.ctu.edu.vn
• 2. tích giảithuật? • Tiêu chuẩnđánh giá giảithuật • Phươngpháp đánh giá • Bài tập 2
• 3. thuật • Đánh giá giải thuật – Tính đúng đắn ● Chạytrên dữliệuthử Chứngminh lý thuyết(bằngtoán họcchẳng hạn) ● – – Tính đơn giản Tính nhanh chóng (thờigian thựcthi) ● Quan trọngkhi chươngtrình đ ư ợ cthựcthi nhiềulầnHiệuquả thờigian thựcthi ● 3
• 4. thờigian thựchiệnchươngtrình – – – – Lậptrình và đo thờigian thựchiện Phụ thuộcvào tậplệnhcủamáy tính K ỹnăng củangườilậptrình Dữliệuđầuvào Tính đ ộphứctạpthờigian thựchiệncủagiải thuật= đ ộ đo sựthựcthi củagiải thuật 4
• 5. thờigian thựchiện: – Hàm T(n) ≥ 0, vớin là kích thước(độlớn)của đầu vào – Ví dụ:T(n) = 3n – Đơnv ịtính: s ốlệnhc ơbản,s ốc h ỉthị,… – Thờigian thựchiệntrong các trườnghợp:tốt nhất,xấu nhất,trung bình So sánh T1(n) và T2(n) 5
• 6. (growth rate): – – – T(n) có t ỷsuấttăng f(n) nếutồntạihằngC > 0 và n0 sao cho T(n)  Cf(n) n  n0 Cho mộthàm không âm T(n), luôn tồntạit ỷsuất tăng f(n) củanó Ví dụ:T(0) = 1, T(1) = 4, T(n) = (n+1)2, ta có: f(n) = n2 (vớiC = 4, n0 = 1) 6
• 7. minhrằng: – T ỷsuấttăng củaT(n) = 3n3 + 2n là n3 ● ChọnC = ?, chọnn0 = ? Chứngminh bằngquy nạp T(n)  Cf(n) n  n0 ● 7
• 8. minhrằng: – T ỷsuấttăng củaT(n) = 3n3 + 2n là n3 ● ChọnC = 5, chọnn0 = 0 Chứngminh bằngquy nạp 3n3 + 2n  5n3 n  0 ● ● Quy tắc: T(n) là đa thứccủan thì t ỷ suấttăng là bậccao nhất củan 8
• 9. giải thuật – – P1 có T1(n) = 100n2 P2 có T2(n) = 5n3 ??? Giảithuậtnào chạynhanh hơn Xét nếun  20 thì T1(n)  T2(n) Xét nếu n  20 thì T1(n)  T2(n)  So sánh t ỷsuấttăng hơnlà so sánh trựctiếpcác hàm T(n) 9
• 10. Ô lớn(big O) – NếuT(n) có t ỷsuấttăng f(n)  T(n) có đ ộphứctạplà f(n) và ký hiệulà O(f(n)), đọclà “ô f(n)”. • Ví dụ:T(n) = (n + 1)2 có đ ộphứctạpO(n2) • Tính chất – – O(cf(n)) = O(f(n)), c: hằngs ố O(C) = O(1) • Đ ộphứctạpcủagiảithuật: hàm chặntrên củathờigian • Mộts ốhàm thểhiệnđ ộphứctạpthườnggặp: log2n, nlog2n, n2, n3, 2n, n!, nn, … 10
• 11.
• 12. Cho 2 chương trình: – – P1 có thờigian thựchiệnT1(n) = O(f1(n)) P2 có thờigian thựchiệnT2(n) = O(f2(n)) • Quy tắccộng: – Thờigian thựcthi P1 và P2 nốitiếpnhau s ẽlà: ● T(n) = T1(n) + T2(n) = O(max(f1(n), f2(n)) ● Quy tắcnhân: – Thờigian thựcthi P1 và P2 lồngnhau (vd: vòng lặp lồngnhau chẳnghạn): ● T(n) = T1(n)  T2(n) = O(f1(n)  f2(n)) 12
• 13. Quy tắcnhân: for (i=1; i<= n; i++) for (j=1; j<=n; j++) { thựchiệncông việcO(1) } T(n) = O(n2 ) 13
• 14. (i=1; i< n; i++) for (j=i+1; j<=n; j++) { thựchiệncông việcO(1) } Áp dụngquy tắcnhân đ ư ợ ckhông? T(n) ???? 14
• 15. Quy tắctổng quát: – – Đọc(read, scanf), ghi (write, printf), lệnhgán, so sánh: thờigian là hằngs ốhayO(1) Lệnh if: if (điều kiện) lệnh 1 else lệnh 2 ● max (lệnh1, lệnh2) + điềukiện – Vòng lặp:tổngthờigian thựchiệnthân vòng lặp ● Trong trườnghợpkhông xác địnhđ ư ợ cs ốlầnlặpta phảilấys ốlần lặptrong trườnghợpxấunhất. 15
• 16. Phươngpháp thực hiện: – – Xác địnhđầuvào: thườngký hiệulà n Cách 1: dùng cho tấtc ảcác loạichươngtrình ● Tính thờigian thựchiệnT(n) cho toàn b ộchương trình  O(f(n)) từT(n) Cách 2: không áp dụngcho chươngtrình đ ệquy – ● Chia chươngtrình nhiềuđoạnnhỏ Tính T(n) và O(f(n)) cho từng đoạn Áp dụngquy tắccộng,quy tắcnhân đ ểcó O(f(n)) cho c ảchương trình ● ● 16
• 17. dụ: 1. void sap_xep(int a[], int n) { 2. int tam; 3. for (int i = 0; i < n; i++) 4. for (int j = i + 1; j < n; j++) 5. if (a[j] < a[i]) { 6. tam = a[i]; 7. a[i] = a[j]; 8. a[j] = tam; 9. } 10. } 17
• 18. dụ: 1. int tim_kiem(int x, int a[], int n) { 2. int found, i; 3. found = 0; 4. i = 0; 5. while (i < n && !found) 6. if (a[i] == x) 7. found = 1; 8. else 9. i = i+1; 10. return i; 11. } 18
• 19. dụ: 1. int tim_kiem_nhi_phan(int x, int a[], int n) { 2. int i = 0, j = n – 1; 3. while (i <= j) { 4. int m = (i + j)/2; 5. 6. if (x == a[m]) return m; 7. if (x < a[m]) 8. j = m – 1; 9. else 10. i = m + 1; 11. } 12. return -1; // khong tim thay 13.} 19
• 20. Chươngtrình có gọichươngtrình con (không đ ệquy) • Quy tắc:tính từtrong ra ngoài • C, B2, B12, B11 • B1 •B •A A B B11 B1 C B2 B12 20
• 21. Chươngtrình đ ệquy – – – Lậpphươngtrình đ ệquy T(n) Giảiphươngtrình đ ệquy tìm nghiệm Suy ra t ỷsuấttăng f(n) hay O(f(n)) Ví dụ: 1. int giai_thua(int n) { 2. if (n == 0) 3. return 1; 4. else 5. 6. } return n * giai_thua(n – 1); 21
• 22. truy hồi – – T riểnkhai T(n) theo T(n - 1) rồiT(n - 2) … cho đếnT(1) hoặc T(0) Suy ra nghiệm • Phươngpháp đoán nghiệm – – Dựđoán nghiệm f(n) Áp dụngđịnhnghĩa t ỷsuấttăng và chứng minh f(n) là t ỷsuấttăng củaT(n) • Áp dụngcông thứcđốivớilớpphươngtrình đ ệquy đã có lờigiải 22
• 23. T riểnkhai T(n) T(n-1) T(n-2) … theo rồiđến tiếp đến cho đếnT(1) 23
• 24. đ ệquy: T(1) = C1 T(n) = 2T(n - 1) + C2 • Ta có: T(n) = 2T(n – 1) + C2 = 2(2T(n – 2) + C2) + C2 = 22T(n – 2) + 2C2 + C2 = 22(2T(n – 3) + C2) + 2C2 + C2 = 23T(n – 3) + 22C2 + 2C2 + C2 = … = 2kT(n – k) + 2k-1C2 + 2k-2C2 + … + 2C2 + C2 Quá trình dừnglạikhi n – k = 1 hay k = n – 1, khi đó: T(n) = 2n-1T(1) + C2 (2n-1 – 1) = C1 2n-1 + C2 (2n-1 – 1) = O(2n) – 24
• 25. = Cn-1 + n C1 = 1 n  2 Triển khai phương trình Cn = Cn-1 + n = Cn-2 + (n – 1) + n = Cn-3 + (n – 2) + (n – 1) + n ... = C1 + 2 + … + (n – 2) + (n – 1) + n = 1 + 2 + … + (n – 1) + n = n(n+1)/2 = n2/2 Ví d ụ2
• 26. = Cn/2 + 1 C1 = 0 n  2 Đặt n = 2k C(2k) = C(2k-1) + 1 = C(2k-2 )+ 1 + 1 = C(2k-3 )+ 3 . . . = C(20 ) + k = C1 + k = k Cn = k = logn Cn  logn Ví d ụ3
• 27. = 2Cn/2 + n C1 = 0 for n  2 Đặt n = 2k C(2k) = 2C(2k-1) + 2k C(2k)/2k = C(2k-1)/ 2k-1 + 1 = C(2k-2)/ 2k-2 + 1 +1 . . = k  C(2k ) = k.2k Cn = nlogn Ví d ụ4
• 28. = 2C(n/2) + 1 C(1) = 0 for n  2 Đặt n = 2k C(2k) = 2C(2k-1) + 1 C(2k)/ 2k = 2C(2k-1)/ 2k +1/2k = C(2k-1)/ 2k-1 + 1/2k + 1/2k-1 ]+ 1/2k =[C(2k-2)/ 2k-2 . . =C(2k-i)/ 2k -i + 1/2k – i +1 + … + 1/2k Ví d ụ5 Cuối cùng, khi i = n -1, ta được: C(2k)/2k = C(2)/2 + 1/4 + …+ 1/2k = 1/2 + 1/4 + ….+1/2k  1  C(2k)  2k = n
• 29. = 2Cn-1 +1 C1 = 1 n  2 Cn + 1 = 2Cn-1 + 2 = 2 (Cn-1 +1) = 2 (2 (Cn-2 + 1)) = 22(Cn-2 +1) ... = 2n-1(C1 + 1) = 2n-1(1 + 1) = 2n Cn = 2n -1 Ví d ụ6
• 30. phương trình C(n)=2C (√n)+logn Đặt m = logn => n = 2m C(2m) = 2C(2m/2) + m Đặt S(m) = C(2m) S(m) = 2S(m/2) + m = mlogm C(n) = logn loglogn
• 31. 1 + 2 + 3 + … + n = n(n+1)/2  n2/2 S = 1 + 22 + 32 + …+ n2 = n(n+1)(2n+1)/6  n3/3 S = 1 + a + a2 + a3 + … + an = (an+1 -1)/(a-1) Nếu 0< a < 1 thì S  1/(1-a) và khi n   thì S tiến về 1/(1-a) S = 1 + 1/2 + 1/3 + … + 1/n = ln(n) + Hằng số Euler   0.577215665 S = 1 + 1/2 + 1/4 + 1/8 + … + 1/2n + …  
• 32. đ ộphứctạpcủalờigiảiđ ệquy – Tính giai thừacủan – Tháp Hà nộivớis ốtầngtháp là n – Tìm kiếmn h ịphân củadãy gồmn s ốđ ư ợ csắptheo thứtựtăng dần 32
• 33. Thửđoán 1 nghiệm f(n) • Sau đó tìm cách chứng minh T(n)  f(n) – Chứng minh mình bằngquynạp • Thông thườngta chọnf(n) có dạng:n, logn, nlogn, 2n , … 33
• 34. Phân rã bài toán lớnthành các bài toán con ● Mộtbài toán lớncó kích thướcn, thành a bài toán con có kích thướcn/b Tổnghợpcác lờigiảicủacác bài toán con đ ểcó đ ượ clời giảicủabài toán lớn – ● Thờigian tổnghợpa bài toán con tốnd(n) thời gian • Phươngtrình đ ệquy cho giảithuậttrên: – – T(1) = 1 T(n) = aT(n/b) + d(n) 34
• 35. truy hồi: T(n) = aT(n/b) + d(n) = a[aT(n/b/b) + d(n/b)] + d(n) = a2T(n/b2) + ad(n/b) + d(n) = a2[aT(n/b3) + d(n/b2)] + ad(n/b) + d(n) = a3T(n/b3) + a2d(n/b2) + ad(n/b) + d(n) = … = akT(n/bk) + aid(n/bi) – Quá trình kếtthúc khi n/bk = 1 hay k = logbn T(n) = ak + aid(n/bi) 35
• 36. solutions ): ak  nlogb a • d(n): hàm tiếntriển(drivingfunction) • Nghiệm chính xác s ẽlà nghiệmchính xác nếu d(n) = 0, vớimọin • Nếud(n) > 0, ta có nghiệm riêng: 36    k1 i0           i0 k1 k1 i0 ) ai d(bk i i i i i b bk  a d b  n  a d
• 37. riêng thì đ ộphứctạplà nghiệm thuần nhất • Nếunghiệm riêng lớnhơnnghiệm thuầnnhất thì đ ộ phứctạplà nghiệmriêng • Tuy nhiên, tính nghiệm không phảilúc nào cũng dễ! 37
• 38. nghiệmriêng trong trườnghợpd(n) có dạngđặcbiệt • Hàm nhân, hàm có tính chấtnhân (multiplicative function): – – Hàm d(n) có tính nhân nếuvà c h ỉnếud(x.y) = d(x).d(y) Ví dụ: ● d(n) = n2 là hàm nhân vì d(x.y) = (x.y)2 = x2 .y2 = d(x).d(y) d(n) = 3n2 không phảilà hàm nhân ● 38
• 39. hàm nhân, ta có nghiệm riêng: 39 1 a d(b) d(b)k   d(b) i0  k1 k1 k1 i ai d(bki )  ai d(b)ki  d(b)k  a  ak i 0 i0
• 40. d(b), ak > [d(b)]k 40 a d(b) ai d (bki )  log a b T (n) O(n logn)  d(b)k k  ak k a  i k d(b) i k i    k 1  i 0 d(b)   k1 k1 i 0 i0 • Nếua < d(b) T(n) • Nếua = d(b) log log a b n b  O(a )  O(n ) k T(n)  O(a ) logd (b) b )  O(n ) logn b  O(d(b) k  O(d(b) )
• 41. phươngtrình đ ệquy sau vớiT(1) = 1 4/
• 42. với T(1) = 1 và ● Phương trình có dạng phương trình tổng quát. d(n)=n là hàm nhân. a = 4 và b = 2. d(b) = b = 2 < a. T(n) = O(nlogb ) = O(n ) = O(n ). a log4 2 ● ● ● ●  2    1/ T(n)  4T n   n
• 43. với T(1) = 1 và  2    2/ T(n)  4T n   n2 ● Phương trình có dạng phương trình tổng quát. d(n)=n2 là hàm nhân. a = 4 và b = 2. d(b) = b2 = 4 = a. T(n) = O(nlogbalogbn) = O(nlog4logn) = O(n2logn). ● ● ● ●
• 44. với T(1) = 1 và  2    3/ T(n)  4T n   n3 ● Phương trình có dạng tổng quát. d(n)=n3 là hàm nhân. a = 4 và b = 2. d(b) = b3 = 8 > a. T(n) = O(nlogbd(b)) = O(nlog8) = O(n3). ● ● ● ●
• 45.
• 46.
• 47. với T(1) = 1 và ● PT thuộc dạng phương trình tổng quát nhưng d(n) = nlogn không phải là một hàm nhân. NTN = nlogba = nlog2 = n Do d(n) = nlogn không phải là hàm nhân nên ta phải tính nghiệm riêng bằng cách xét trực tiếp ● ●  2    T(n)  2T n   nlogn
• 48. giải phương trình đệ quy tổng quát thì n = bk nên k = logbn, ở đây do b = 2 nên 2k = n và k = logn, NR= O(nlog2n) > NTN T(n) = O(nlog2n). ● ● k-j k-1 j=0 j k-j k-1 aj dbk-j  2 2 log2 NR  ∑ j0 2 NR  2k (k - j)  2k k(k 1)  O(2k k2 ) k-1 j0
• 49. T(1) = 1 và ● Phương trình có dạng phương trình tổng quát d(n)=1 là hàm nhân a = 1 và b = 2 d(b) = 1 = a T(n) = O(nlogb logbn) = O(n logn) = O(logn) a log1 ● ● ● ● T(n)=T n 2 ()+1
• 50. T(1) = 1 và  2    T(n)  2T n   logn ● Phương trình có dạng tổng quát d(n)=logn không phải là hàm nhân NTN = O(nlogba)=O(nlog2)=O(n) Tính trực tiếp nghiệm riêng ● ● ●
• 51. a j d(bk  j )  2 j log2k j j0 j 0 k1 k1 k1 NR  2j (k  j)  k2j   j2 j j0 j0 j 0 ) 2 1 1 2k NR  O(k k1 j0 j 2 )  O(k NR  O(k2k )  O(n log n)  n  NTN T(n)=O(nlogn) Ví dụ (tt)
• 52.
• 53. củađoạnchương trình sau theo n: 1.int max(int a[], int n) { 2. if (n == 1) 3. return a[0]; 4. if (a[n-1] > max(a, n - 1)) 5. return a[n-1]; 6.return max(a, n-1); 7.} 53