Bài giảng Phân tích thiết kế thuật toán - Chương 1: Kỹ thuật phân tích giải thuật

1 KỸ THUẬT PHÂN TÍCH GIẢI THUẬT • Tại sao cần phải phân tích giải thuật ? • Tiêu chuẩn đánh giá giải thuật • Phương pháp đánh giá • Bài tập 2 • Với phần lớn các bài toán, thường có nhiều giải thuật khác nhau để giải một bài toán. • Làm cách nào để chọn giải thuật tốt nhất để giải một bài toán? • Làm cách nào để so sánh các giải thuật cùng giải được một bài toán? => Cần đánh giá giải thuật để lựa chọn giải thuật tốt nhất. 3 • Đánh giá giải thuật - Tính đúng đắn • Chạy trên dữ liệu thử • Chứng minh lý thuyết (bằng toán học chẳng hạn) - Tính đơn giản - Tính nhanh chóng (thời gian thực thi) • Quan trọng khi chương trình được thực thi nhiều lần, chương trình có khối lượng dữ liệu nhập lớn. • Hiệu quả thời gian thực thi -> Thường chỉ sử dụng vài lần 4 • Đo thời gian thực hiện chương trình - Lập trình và đo thời gian thực hiện - Phụ thuộc vào tập lệnh của máy tính - Kỹ năng của người lập trình - Dữ liệu đầu vào Tính độ phức tạp thời gian thực hiện của giải thuật = độ đo sự thực thi của giải thuật  Độ phức tạp thời gian thực hiện của giải thuật thường được tính trong trường hợp xấu nhất. 5 • Đo thời gian thực hiện: - Hàm T(n) ≥ 0  n  0, với n là kích thước (độ lớn) của dữ liệu đầu vào - Ví dụ: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số. - Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(n). • Đơn vị đo thời gian thực hiện - Ví dụ: Khi ta nói thời gian thực hiện của một chương trình là T(n) = Cn thì có nghĩa là chương trình ấy cần Cn chỉ thị thực thi. - Đơn vị tính: số lệnh cơ bản, số chỉ thị, 6 • Thời gian thực hiện chương trình không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. • Dữ liệu vào có cùng kích thước nhưng thời gian thực hiện chương trình có thể khác nhau. - Ví dụ: chương trình sắp xếp dãy số nguyên tăng dần. Nhập vào dãy số nguyên. => Dãy số nhập vào có thể: có thứ tự, chưa có thứ tự, có thứ tự tăng hoặc có thứ tự giảm. => Thời gian thực hiện trong các trường hợp: tốt nhất, xấu nhất, trung bình 7 • Tỷ suất tăng (growth rate): - T(n) có tỷ suất tăng f(n) nếu tồn tại hằng C > 0 và n0 sao cho T(n)  Cf(n) n  n0 - Cho một hàm không âm T(n), luôn tồn tại tỷ suất tăng f(n) của nó - Ví dụ: T(0) = 1, T(1) = 4, T(n) = (n+1)2, Đặt n0 = 1 và c = 4 thì với mọi n ≥ 1, ta có T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, => Tỷ suất tăng của T(n) là n2. 8 • Ví dụ: chứng minh rằng: Tỷ suất tăng của T(n) = 3n3 + 2n2 là n3 Giải – Chọn n0 = 0 và C = 5 với mọi n ≥ 0, ta có 3n3 + 2n2 ≤ 5n3 Tỷ suất tăng của T(n) là n3. • Quy tắc: T(n) là đa thức của n thì tỷ suất tăng là bậc cao nhất của n 9 • Cho 2 giải thuật - P1 có T1(n) = 100n2  tỷ suất tăng là - P2 có T2(n) = 5n3  tỷ suất tăng là Giải thuật nào chạy nhanh hơn ?  So sánh tỷ suất tăng hơn là so sánh trực tiếp các hàm T(n) Xét nếu n  20 thì T1(n) > T2(n) Xét nếu n  20 thì T1(n)  T2(n)  phụ thuộc vào kích thước dữ liệu vào. 10 n2 n3 • Ký hiệu Ô lớn (big O) – Nếu T(n) có tỷ suất tăng f(n) -> T(n) có độ phức tạp là f(n) và ký hiệu là O(f(n)), đọc là “ô của f(n)”. • Ví dụ: T(n) = (n + 1)2 có tỷ suất tăng là n2 nên hàm T(n) có độ phức tạp O(n2) • Tính chất – O(cf(n)) = O(f(n)), c: hằng số – O(C) = O(1) • Độ phức tạp của giải thuật: hàm chặn trên của thời gian • Một số hàm thể hiện độ phức tạp thường gặp: log2n, n, nlog2n, n 2, n3, 2n, n!, nn. 11 logN N NlogN n2 12 • Các hàm: log2n, n, nlog2n gọi là hàm đa thức • Ba hàm cuối cùng: 2n, n!, nn gọi là dạng hàm mũ, • Nhận xét: – Một giải thuật mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện – Các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật 13 • Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến hiệu quả của thời gian thực hiện của chương trình nên ta có thể xem việc xác định thời gian thực hiện của chương trình chính là xác định độ phức tạp của giải thuật. 14 • Cho 2 chương trình: - P1 có thời gian thực hiện T1(n) = O(f1(n)) - P2 có thời gian thực hiện T2(n) = O(f2(n)) • Quy tắc cộng: - Thời gian thực thi P1 và P2 nối tiếp nhau sẽ là: + T(n) = T1(n) + T2(n) = O(max(f1(n), f2(n)) - Ví dụ: + Lệnh gán x:=15 tốn một hằng thời gian hay O(1) + Lệnh đọc dữ liệu READ(x) tốn một hằng thời gian hay O(1) 15 Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1) • Quy tắc nhân: – Thời gian thực thi P1 và P2 lồng nhau (vd: vòng lặp lồng nhau chẳng hạn): • T(n) = T1(n) x T2(n) = O(f1(n) x f2(n)) – Ví dụ: 16 for (i=1; i<= n; i++) for (j=1; j<=n; j++) { thực hiện công việc O(1) } T(n) = O(n2) • Quy tắc tổng quát: - Đọc (read, scanf), - Ghi (write, printf), - Lệnh gán, so sánh: - Lệnh if: if (điều kiện) else lệnh 2  max (lệnh 1, lệnh 2) + điều kiện 17  Thường thời gian kiểm tra điều kiện là O(1)  Thời gian là hằng số hay O(1) lệnh 1 - Vòng lặp: Tổng thời gian thực hiện thân vòng lặp + Trong trường hợp không xác định được số lần lặp ta phải lấy số lần lặp trong trường hợp xấu nhất. 18 + Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp. • Phương pháp thực hiện: - Xác định đầu vào: thường ký hiệu là n - Cách 1: dùng cho tất cả các loại chương trình + Tính thời gian thực hiện T(n) cho toàn bộ chương trình  O(f(n)) từ T(n) - Cách 2: không áp dụng cho chương trình đệ quy + Chia chương trình nhiều đoạn nhỏ + Tính T(n) và O(f(n)) cho từng đoạn + Áp dụng quy tắc cộng, quy tắc nhân để có O(f(n)) cho cả chương trình 19 • Ví dụ : Tính thời gian thực hiện của đoạn chương trình sắp xếp “nổi bọt” procedure Bubble (var a: array[1..n] of integer); var i,j,temp: integer; begin {1} for i:=1 to n-1 do {2} for j:=n downto i+1 do {3} if a[j-1]>a[j] then begin { đổi chổ a[i], a[j] } {4} temp:=a[j-1]; {5} a[j-1]:=a[j]; {6} a[j]:=temp; end; end; 20 2) do đó lệnh {3} tốn O(1). 3) Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1),  do đó vòng lặp {2} tốn O((n-i).1)=O(n-i). 1) Cả ba lệnh đổi chỗ {4} {5} {6} tốn O(1) thời gian 4) Vòng lặp {1} lặp (n-1) lần  Cả ba lệnh đổi chỗ {4} {5} {6} tốn O(1) thời gian, do đó lệnh {3} tốn O(1).  Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1). Do đó vòng lặp {2} tốn O((n-i).1)=O(n-i).  Vòng lặp {1} lặp (n-1) lần vậy độ phức tạp của giải thuật là: 21  Ví dụ : Tính thời gian thực hiện của đoạn chương trình sắp xếp “nổi bọt” procedure Bubble (var a: array[1..n] of integer); var i,j,temp: integer; begin {1} for i:=1 to n-1 do {2} for j:=n downto i+1 do {3} if a[j-1]>a[j] then begin // đổi chổ a[i], a[j] {4} temp:=a[j-1]; {5} a[j-1]:=a[j]; {6} a[j]:=temp; end; end;    1 2 1 1 ( ) ( ) 2 n i n n T n n i O n                 1 1 1 n 1 n 2 .. n k 1 ... 1 2 n i n n n i                • Ví dụ: Tìm kiếm tuần tự. Hàm tìm kiếm Search nhận vào một mảng a có n số nguyên và một số nguyên x, hàm sẽ trả về giá trị logic TRUE nếu tồn tại một phần tử a[i] = x, ngược lại hàm trả về FALSE. – Giải thuật tìm kiếm tuần tự là lần lượt so sánh x với các phần tử của mảng a, • Bắt đầu từ a[1], nếu tồn tại a[i] = x thì dừng và trả về TRUE, • Ngược lại nếu tất cả các phần tử của a đều khác X thì trả về FALSE. 22 • Ví dụ: Hàm tìm kiếm tuần tự. FUNCTION Search(a:ARRAY[1..n] OF Integer; x:Integer):Boolean; VAR i:Integer; Found:Boolean; BEGIN {1} i:=1; {2} Found:=FALSE; {3} WHILE (i<=n) AND (not Found) DO {4} IF A[i]=X THEN Found:=TRUE ELSE i:=i+1; {5} Search:=Found; END; 23  Các lệnh {1}, {2}, {3} và{5} nối tiếp nhau,  Ba lệnh {1}, {2} và {5} đều có độ phức tạp O(1)  Do đó độ phức tạp của hàm Search chính là độ phức tạp lớn nhất trong 4 lệnh này.  Lệnh {4} có độ phức tạp O(1)  Lệnh {3} thực hiện n lần  Vậy ta có T(n) = O(n). • Chương trình có gọi chương trình con (không đệ quy) • Quy tắc: tính từ trong ra ngoài • Tính thời gian thực hiện của C, B2, B11 và B12. • Tính thời gian thực hiện của B1. • Tính thời gian thực hiện của B. • Tính thời gian thực hiện của A. A B B1 B11 C B2 B12 24 • Để tính thời gian thực hiện của A, ta tính theo các bước sau: • Ví dụ: Ta có thể viết lại chương trình sắp xếp bubble như sau: – Trước hết chúng ta viết thủ tục Swap để thực hiện việc hoàn đổi hai phần tử cho nhau, – Sau đó trong thủ tục Bubble, khi cần ta sẽ gọi đến thủ tục Swap này. PROCEDURE Swap (VAR x, y: Integer); VAR temp: Integer; BEGIN temp := x; x := y; y := temp; END; 25 PROCEDURE Bubble (VAR a: ARRAY[1..n] OF integer); VAR i,j :Integer; BEGIN {1} FOR i:=1 TO n-1 DO {2} FOR j:=n DOWNTO i+1 DO {3} IF a[j-1]>a[j] THEN Swap(a[j-1], a[j]); END; 26 Cách tính độ phức tạp PROCEDURE Swap (VAR x, y: Integer); VAR temp: Integer; BEGIN temp := x; x := y; y := temp; END; PROCEDURE Bubble (VAR a: ARRAY[1..n] OF integer); VAR i,j :Integer; BEGIN {1} FOR i:=1 TO n-1 DO {2} FOR j:=n DOWNTO i+1 DO {3} IF a[j-1]>a[j] THEN Swap(a[j-1], a[j]); END; 27  Chương trình Bubble gọi chương trình con Swap  Thời gian thực hiện của Swap là O(1) vì nó chỉ bao gồm 3 lệnh gán  Trong Bubble, lệnh {3} gọi Swap nên chỉ tốn O(1)  Lệnh {2} thực hiện n-i lần, mỗi lần tốn O(1), nên tốn O(n-i).  Lệnh {1} thực hiện n-1 lần nên    1 2 1 1 ( ) ( ) 2 n i n n T n n i O n        • Với các chương trình có gọi các chương trình con đệ quy, ta không thể áp dụng cách tính như trình bày phần trước vì một chương trình đệ quy sẽ gọi chính bản thân nó. • Chương trình đệ quy có thể minh họa như hình ảnh sau: 28 • Chương trình đệ quy - Lập phương trình đệ quy T(n) - Giải phương trình đệ quy tìm nghiệm - Suy ra tỷ suất tăng f(n) hay O(f(n)) 1. int giai_thua(int n) { 2. if (n == 0) 3. return 1; 4. else 5. return n * giai_thua(n - 1); 6. } 29 Ví dụ: • Phương trình đệ quy là một phương trình biểu diễn mối liên hệ giữa T(n) và T(k), trong đó – T(n) là thời gian thực hiện chương trình với kích thước dữ liệu nhập là n, – T(k) thời gian thực hiện chương trình với kích thước dữ liệu nhập là k, với k < n. – Để thành lập được phương trình đệ quy, ta phải căn cứ vào chương trình đệ quy. 30 • Thông thường đối với một chương trình đệ quy để giải bài toán kích thước n, – phải có ít nhất một trường hợp dừng ứng với một n cụ thể – và lời gọi đệ quy để giải bài toán kích thước k (k<n). 31 • Để thành lập phương trình đệ quy, ta gọi – T(n) là thời gian để giải bài toán kích thước n – T(k) là thời gian để giải bài toán kích thước k • Khi đệ quy dừng, ta phải xem xét khi đó chương trình làm gì và tốn hết bao nhiêu thời gian, chẳng hạn thời gian này là c(n) • Khi đệ quy chưa dừng thì phải xét xem có bao nhiêu lời gọi đệ quy với kích thước k ta sẽ có bấy nhiêu T(k) – Ngoài ra ta còn phải xem xét đến thời gian để phân chia bài toán và tổng hợp các lời giải, chẳng hạn thời gian này là d(n). 32 • Dạng tổng quát của một phương trình đệ quy sẽ là: • Trong đó: – C(n) là thời gian thực hiện chương trình ứng với trường hợp đệ quy dừng – F(T(k)) là một đa thức của các T(k). – d(n) là thời gian để phân chia bài toán và tổng hợp các kết quả. 33 ( ) ( ) ( ( )) ( ) C n T n F T k d n     • Ví dụ: Xét hàm tính giai thừa viết bằng giải thuật đệ quy như sau: Function Giai_thua(n:integer): integer; Begin if n=0 then Giai_thua :=1 else Giai_thua := n*Giai_thua(n-1); End; 34 function Giai_thua(n:integer): integer; begin if n=0 then Giai_thua :=1 else Giai_thua := n*Giai_thua(n-1); end; 35  Gọi T(n) là thời gian thực hiện việc tính n giai thừa  T(n-1) là thời gian thực hiện việc tính n-1 giai thừa  Trường hợp n=0 thì chương trình chỉ thực hiện một lệnh gán Giai_thua:=1 nên tốn O(1), do đó ta có T(0) = C1  Trường hợp n>0 chương trình phải gọi đệ quy Giai_thua(n-1), việc gọi đệ quy này tốn T(n-1)  Sau khi có kết quả của việc gọi đệ quy, chương trình phải nhân kết quả đó với n và gán cho Giai_thua  Thời gian để thực hiện phép nhân và phép gán là một hằng C2.  Vậy ta có phương trình đệ quy để tính thời gian thực hiện của chương trình đệ quy Giai_thua là: 1 2 ê 0 ( ) ( 1) ê 0 C n u n T n T n C n u n       • Có ba phương pháp giải phương trình đệ quy: 1. Phương pháp truy hồi 2. Phương pháp đoán nghiệm. 3. Lời giải tổng quát của một lớp các phương trình đệ quy. 36 • Phương pháp truy hồi - Triển khai T(n) theo T(n - 1) rồi T(n - 2) cho đến T(1) hoặc T(0) - Suy ra nghiệm • Phương pháp đoán nghiệm - Dự đoán nghiệm f(n) - Áp dụng định nghĩa tỷ suất tăng và chứng minh f(n) là tỷ suất tăng của T(n) • Áp dụng công thức đối với lớp phương trình đệ quy đã có lời giải 37 • Triển khai T(n) theo T(n-1) rồi đến T(n-2) tiếp đến cho đến T(1) 38 • Ví dụ: Giải phương trình • Ta có T(n) = T(n-1) + C2 T(n) = [T(n-2) + C2] + C2 = T(n-2) + 2C2 T(n) = [T(n-3) + C2] + 2C2 = T(n-3) + 3C T(n) = T(n-i) + iC2 • Quá trình trên kết thúc khi n - i = 0 hay i = n. Khi đó ta có T(n) = T(0) + nC2 = C1 + n C2 = O(n) 39 1 2 ê 0 ( ) ( 1) ê 0 C n u n T n T n C n u n       • Ví dụ: Giải phương trình • Ta có T(n) = 2T( ) + C2n T(n) = 2[2T( )+ C2( )] + C2n = 4T( )+ 2C2n T(n) = 4[2T( )+ C2( )] + 2C2n = 8T( )+ 3C2n . T(n) = 2iT( )+ iC2n • Quá trình suy rộng sẽ kết thúc khi = 1 hay 2i = n và do đó i = logn. Khi đó ta có: T(n) = nT(1) + lognC2n = C1n + C2nlogn = O(nlogn). 40 1 2 ê 1 ( ) 2 ( ) ê 1 2 C n u n T n n T C n n u n        2 n 4 n 2 n 2 n 8 n 4 n 8 n 2i n 2i n • 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ằng quy nạp • Thông thường ta chọn f(n) có dạng: n, logn, nlogn, 2n, 41 • Giải thuật chia để trị: - Phân rã bài toán lớn thành các bài toán con + Một bài toán lớn có kích thước n, thành a bài toán con có kích thước n/b - Tổng hợp các lời giải của các bài toán con để có được lời giải của bài toán lớn + Thời gian tổng hợp a bài toán con tốn d(n) thời gian • Phương trình đệ quy cho giải thuật trên: 42 1 ê 1 ( ) ( ) ( ) ê 1 n u n T n n aT d n n u n b       • Áp dụng phương pháp 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) = - Quá trình kết thúc khi = 1 hay k = logbn 43 1 0 ( ) a d( ) k k j k j j n n a T b b      1 0 ( ) a d( ) k k j k j j T n a b       k n b • Nghiệm thuần nhất (homogeneous solutions ): • d(n): hàm tiến triển (driving function) • Nếu d(n) = 0, nghiệm thuần nhất là nghiệm chính xác, với mọi n • Nếu d(n) > 0, ta có nghiệm riêng: 44 logb aka n 1 0 a d( ) k j k j j b     1 0 ( ) a d( ) k k j k j j T n a b       1 ê 1 ( ) ( ) ( ) ê 1 n u n T n n aT d n n u n b       • Nếu nghiệm thuần nhất lớn nghiệm riêng thì độ phức tạp là nghiệm thuần nhất • Nếu nghiệm riêng lớn hơn nghiệm thuần nhất thì độ phức tạp là nghiệm riêng • Tuy nhiên, tính nghiệm không phải lúc nào cũng dễ! 45 • Ta sẽ tính nghiệm riêng trong trường hợp d(n) có dạng đặc biệt • Hàm nhân, hàm có tính chất nhân (multiplicative function): - Hàm d(n) có tính nhân nếu và chỉ nếu d(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ải là hàm nhân 46 • Nếu d(n) là hàm nhân, ta có nghiệm riêng: 47 • Hay nghiệm riêng • Trường hợp 1: Nếu a > d(b), ak > [d(b)]k • Trường hợp 2: Nếu a < d(b), ak < [d(b)]k • Trường hợp 2: Nếu a = d(b), 48 log log ( ) ( ) ( ) ( )b b n akT n O a O a O n   log log ( ) ( ) ( ( ) ) ( ( ) ) ( )b b n d bkT n O d b O d b O n   log ( ) ( log )b a bT n O n n • Giải các phương trình đệ quy sau với T(1) = 1 49 Ví dụ: GPT với T(1) = 1 và - Phương trình có dạng phương trình tổng quát. - a = 4 và b = 2. - d(b) = b = 2 < a = 4 - T(n) = O(nlogb a) = O(nlog4) = O(n2). 50 - d(n)=n là hàm nhân. Ví dụ: GPT với T(1) = 1 và 16/06/2014 - 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(nlogb alogbn) = O(nlog4logn) = O(n2logn). 51 Ví dụ: GPT với T(1) = 1 và  Phương trình có dạng phương trình 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(nlogb d(b)) = O(nlog8) = O(n3). 52 Ví dụ: GPT với T(1) = 1 và 16/06/2014 - 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. - Nghiệm thuần nhất = nlogb a = 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 53 1 0 a d( ) k j k j j b     - Theo giải phương trình đệ quy tổng quát thì n = bk nên k = logbn, ở đây do b = 2 nên 2 k = n và k = logn, - NR= O(nlog2n) > NTN = n - Vậy O(nlog2n) 54 1 1 0 0 a d( ) 2 2 log 2 k k j k j j k j k j j j NR b           1 2 0 ( 1) 2 ( ) log 2 2 (2 ) 2 k k k k j k k NR k j O k        Bài tập • Bài 1: Tính thời gian thực hiện của các đoạn chương trình sau: a) Tính tổng của các số Sum := 0; for i:=1 to n do begin readln(x); Sum := Sum + x; end; 55 Bài tập • Bài 1: Tính thời gian thực hiện của các đoạn chương trình sau: b) Tính tích hai ma trận vuông cấp n C = A*B: for i := 1 to n do for j := 1 to n do begin c[i,j] := 0; for k := 1 to n do c[i,j] := c[i,j] + a[i,k] * b[k,j]; end; 56 Bài tập • Bài 2: Giải các phương trình đệ quy sau với T(1) = 1 và a) T(n) = 3T(n/2) + n b) T(n) = 3T(n/2) + n2 c) T(n) = 8T(n/2) + n3 57 Bài tập • Bài 3: Giải các phương trình đệ quy sau với T(1) = 1 và a) T(n) = 4T(n/3) + n b) T(n) = 4T(n/3) + n2 c) T(n) = 9T(n/3) + n2 58 Bài tập • Bài 4: Giải các phương trình đệ quy sau với T(1) = 1 và a) T(n) = T(n/2) + 1 b) T(n) = 2T(n/2) + logn c) T(n) = 2T(n/2) + n d) T(n) = 2T(n/2) + n2 59