Bài giảng phân tích thiết kế thuật toán năm 2024

• 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 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

Phân tích và thiết kế thuật toán là gì?

Phân tích và thiết kế thuật toán là học phần bắt buộc chuyên ngành Công nghệ thông tin. Học phần này giới thiệu các kỹ thuật phục vụ cho thiết kế và phân tích hiệu quả các thuật toán, nhấn mạnh vào các phương pháp hữu dụng trong thực tế.

Khái niệm thuật toán là gì?

Thuật toán là gì? thuật toán hay còn gọi là giải thuật được hiểu một cách đơn giản là một tập hợp hữu hạn bao gồm các hướng dẫn được xác định rõ ràng, thực hiện được bằng máy tính, thường được dùng để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính nào đó.

Thuật toán trên máy tính là gì?

Trong toán học và khoa học máy tính, thuật toán máy tính, hay còn gọi là giải thuật, là một tập hợp các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, nhằm giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.

Lỗi thuật toán là gì?

Một lỗi trong chuỗi hoặc logic được gọi là lỗi thuật toán. Có nhiều lý do có thể gây nên lỗi này, ví dụ như thuật toán sai, thiếu lệnh, dữ liệu không chính xác hoặc lỗi code. Thông thường, một lệnh bị thiếu sẽ được nhà phát triển giải quyết một cách dễ dàng.