Bài giảng Cấu trúc dữ liệu và giải thuật: Giới thiệu thuật toán và đánh giá thuật toán

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Lý thuyết Phần 1 (Chương 1, 2, 9, 10) „ Giới thiệu thuật toán và đánh giá thuật toán „ Hàm mũ hàm logarit , „ Tính đệ quy và thuật toán đệ quy Vũ Anh Dũng - Khoa CNTT 2 Thuật toán „ Giới thiệu thuật toán và đánh giá thuật toán „ Thuật toán : Tập các chỉ thị với cấu trúc điều khiển mà dựa vào đó các chỉ thị được tiến hành. „ Tính chất : „ Rõ ràng „ Đúng „ Dừng Vũ Anh Dũng - Khoa CNTT 3 Thuật toán „ Giới thiệu thuật toán và đánh giá thuật toán „ Xét bài toán tìm phần tử lớn thứ k trong mảng „ Sắp xếp giảm dần toàn mảng „ Sắp xếp k phần tử đầu tiên và chèn dần „ Chương 7 giới thiệu 1 thuật toán đủ tốt „ Xét bài toán trò chơi ô chữ Vũ Anh Dũng - Khoa CNTT 4 Thuật toán ¾ Có thể đánh giá dựa trên thời gian chạy ¾ Làm thế nào để đánh giá thời gian chạy của một chương trình? ¾ Đánh giá thời gian chạy không thực sự dựa trên mã lệnh của chúng. Vũ Anh Dũng - Khoa CNTT 5 Một số hàm toán học „ Hàm mũ „ Hàm logarit „ Chuỗi số ồ„ Phép đ ng dư „ a mod b Vũ Anh Dũng - Khoa CNTT 6 Chứng minh „ Quy nạp P(n) = 1+2+3+ +n = n(n+1)/2 ….. „ Phản chứng ớ ố ê d bấ kì ó íV i 16 s nguy n ương t ta c t nhất hiệu của 2 số trong đó chia hết h 15c o Vũ Anh Dũng - Khoa CNTT 7 Đệ quy và giải thuật đệ quy „ Khái niệm : Ta nói một đối tượng là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng chính nó. „ Ví dụ : „ người giàu, màn hình TV. „ Số tự nhiên : 1 là ố t hiê„ s ự n n „ X là số tự nhiên nếu X-1 là số tự nhiên „ Giai thừa Vũ Anh Dũng - Khoa CNTT 8 „ Ví dụ hàm sau : 2)1(2)( xxfxf +−= Đệ quy và giải thuật đệ quy „ Giải thuật đệ quy và thủ tục đệ quy : „ Nếu lời giải của bài toán T được thực hiện bằng lời giải của bài toán T’ có dạng giống T, thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ quy Điểm chú ý là T’ phải “nhỏ hơn” T . . ¾ Trường hợp cơ sở ¾ Tạo tiến trình ế„ Đệ quy trực ti p (directly rescursive) : Chứa lời gọi trực tiếp đến chính nó. „ Đệ quy gián tiếp (indirectly rescursive) : Chứa lời gọi Vũ Anh Dũng - Khoa CNTT 9 đến một hàm khác, mà hàm khác lại gọi đến nó. Đệ quy và giải thuật đệ quy „ Thiết kế giải thuật đệ quy : „ Hàm N! „ Hàm Fibonaci „ F(n) = 1 nếu n<=2 „ F(n) = F(n-2) + F(n-1) if n>2 „ Viết một số theo thứ tự ngược lại. Ví dụ : 2893 được viết lại là 3982 Vũ Anh Dũng - Khoa CNTT 10 Đệ quy và giải thuật đệ quy 1 void printOut( int n ) // In số n không âm 2 { 3 printDigit( n % 10 ); 4 if( n >= 10 ) 5 printOut( n / 10 ); 6 7 } Vũ Anh Dũng - Khoa CNTT 11 Đệ quy và giải thuật đệ quy * „ Bài toán “Tháp Hà Nội” „ Phát biểu bài toán : „ Có 3 cọc, cần chuyển đĩa từ cọc A sang cọc C „ Cọc trung gian B „ Mỗi lần chỉ được chuyển 1 đĩa „ Không bao giờ có trường hợp đĩa to ở trên đĩa nhỏ „ Tất cả các đĩa có kĩch cỡ khác nhau Vũ Anh Dũng - Khoa CNTT 12 Đệ quy và giải thuật đệ quy * „ Đệ quy quay lui (back tracking): „ Bài toán tổ hợp chỉnh hợp , „ Bài toán người mua hàng „ Bài toán tám quân hậu Vũ Anh Dũng - Khoa CNTT 13 Đánh giá thuật toán „ Thuật toán đòi hỏi bao nhiêu tài nguyên về không gian và thời gian? „ Làm sao để ước lượng thời gian chạy của một chương trình? Vũ Anh Dũng - Khoa CNTT 14 Các định nghĩa Định nghĩa 2.1. T(N) = O(f(N)) nếu có các hằng số dương c và n0 sao cho T(N) ≤ cf(N) khi N ≥ n0. Định nghĩa 2 2 . . T(N) = Ω(g(N)) nếu có các hằng số dương c à h ( ) ( ) khv n0 sao c o T N ≥ cg N i N ≥ n0. Vũ Anh Dũng - Khoa CNTT 15 T(N) là đại lượng tổng quát của tài nguyên cần dùng Các định nghĩa Định nghĩa 2.3. T(N) = Ө (h(N)) nếu và chỉ nếu T(N) = O(h(N)) và T(N) = Ω(h(N)). Định nghĩa 2 4 . . T(N) = o(p(N)) nếu với mọi hằng số c tồn tại ộ h ( ) ( ( )) khm t n0 sao c o T N n0. Đơn giản hơn T(N) = o(p(N)) nếu T(N) = O( ( )) à ( ) Ө( ( )) Vũ Anh Dũng - Khoa CNTT 16 p N v T N ≠ p N . Đánh giá thuật toán „ Khi T(N) = O(f(N)), là T(N) tăng với tỉ lệ không nhanh hơn f(N); do vậy f(N) là biên trên của T(N). „ Do điều này ngụ ý rằng f(N) = Ω(T(N)), chúng ta nói rằng T(N) là biên dưới của f(N) . Vũ Anh Dũng - Khoa CNTT 17 Đánh giá thuật toán „ Ví dụ : T(N) = 1000N, n0 = 1000, c=1, f(N)=N2 „ N3 tăng nhanh hơn N2, nên ta có thể nói rằng N2 = O(N3) hay N3 =Ω(N2) „ Xét g(N) = 2N2, thì g(N) = O(N3), và g(N) O(N2) đều đúng về mặt kỹ thuật nhưng= lựa chọn O(N2)là đáp án tốt nhất. Vũ Anh Dũng - Khoa CNTT 18 Các quy tắc Quy tắc 1. Nếu T1(N) = O(f(N)) và T2(N) = O(g(N)) thì , (a) T1(N) + T2(N) = O(f(N) + g(N)) ( hay max(O(f(N)) O(g(N))) ), , (b) T1(N) * T2(N) = O(f(N) *g(N)). Quy tắc 3 . LogkN = O(N) đối với hằng số k bất kì. Điều này ói lê ằ á hà l it tă ất hậ Vũ Anh Dũng - Khoa CNTT 19 n n r ng c c m ogar ng r c m Độ phức tạp „ độ phức tạp hằng số, O(c). Số phép tính/thời gian chạy/dung lượng bộ nhớ không phụ thuộc vào độ lớn đầu vào. „ độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào. Chẳng hạn như tính tổng các phần tử của một mảng một chiều. „ độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên). Chẳng h hư á th tá tí h t á ới ả hiề hiề (tí h đị h thứạn n c c ao c n o n v m ng n u c u n n c ma trận). „ độ phức tạp logarit, O(logn) (chú ý: bậc của nó thấp hơn so với O(n)) . Chẳng hạn thuật toán Euclid để tìm ước số chung lớn nhất. „ độ phức tạp hàm bậc 2, O(N2). „ độ phức tạp hàm mũ, O(2n). Trường hợp này bất lợi nhất và sẽ rất phi thực tế nếu thực hiện thuật toán với độ phức tạp này. Vũ Anh Dũng - Khoa CNTT 20 Độ phức tạp „ Không nên nói T(N) = O(2N2) hay T(N) = 0(N2 – 4 – N). „ Trong cả hai trường hợp này, dạng đúng là T(N) = O(N2) . „ Nói chung có thể bỏ qua các số hạng bậc thấp và vứt bỏ các hằng số Vũ Anh Dũng - Khoa CNTT 21 Bài toán tổng dãy con lớn nhất „ Cho các số nguyên (có thể âm) A1, A2, . . . , A ì iá ị lớ hấ ủN t m g tr n n t c a ∑ j kA Ví d Với đầ à 2 11 4 13 5 2 =ik „ ụ: u v o - , , - , , - , - , đáp án là 20 (A2 đến A4) Vũ Anh Dũng - Khoa CNTT 22 Bài toán tổng dãy con lớn nhất Đầu vào Thời gian thuật toán 1 2 3 4 Cỡ O(N3) O(N2) O(NlogN) O(N) N = 10 0.000009 0.000004 0.000006 0.000003 N = 100 0.002580 0.000109 0.000045 0.000006 N = 1000 2.281013 0.010203 0.000485 0.000031 N = 10000 NA 1.2329 0.005712 0.000317 N 100000 NA 135 0.064618 0.003206 = Thời gian chạy ứng với các thuật toán khác nhau Vũ Anh Dũng - Khoa CNTT 23 Cách tính thời gian chạy „ Viết đoạn chương trình tính : ∑N 3 int sum( int n ) =i i 1 { int partialSum; 1 partialSum = 0; 2 for( int i = 1; i <= n; i++ ) 3 partialSum += i * i * i; 4 return partialSum; Vũ Anh Dũng - Khoa CNTT 24 } Cách tính thời gian chạy „ Phân tích : „ Các khai báo không chiếm thời gian. „ Các dòng 1 và 4 được tính mỗi dòng một đơn vị thời gian. „ Dòng 3 được tính bốn đơn vị thời gian thực hiện (hai phép nhân, một phép cộng, và một phép gán) và dòng này được thực hiện N lần, nâng tổng thời gian chạy lên 4N đơn vị. „ Dòng 2 Nn chứa thời gian khởi tạo i, kiểm tra i < N , và tăng i. Thời gian của các thao tác này gồm 1 cho việc khởi tạo, N + 1 cho các kiểm tra, và N cho các phép tăng, tổng cộng là 2N + 2. „ Chúng ta còn chưa kể đến thời gian gọi hàm và trả về giá trị nên tổng cộng thời gian lên đến 6N + 4. Vũ Anh Dũng - Khoa CNTT 25 „ Do vậy, chúng ta kết luận hàm của thời gian chạy là O(N ). Các quy tắc „ Quy tắc 1 – các vòng lặp FOR. Thời gian chạy của một vòng lặp for là thời gian chạy của các lệnh bên trong vòng lặp (kể cả các phép kiểm tra) nhân với số lần lặp. Q tắ 2 Cá ò lặ lồ h„ uy c – c v ng p ng n au Phân tích các vòng lặp này từ trong ra ngoài. Tổng thời gian chạy của một câu lệnh trong một nhóm các vòng lặp lồng nhau là thời gian chạy của lệnh này nhân với cỡ của các vòng lặp. Vũ Anh Dũng - Khoa CNTT 26 Các quy tắc „ Quy tắc 3 – Các lệnh tuần tự. Đối với những lệnh này, chỉ đơn thuần là cộng dồn „ Quy tắc 4 – if/else if(condition) S1 l S2e se Thời gian chạy không bao giờ vượt quá thời gian chạy phép kiểm tra điều kiện cộng với thời gian chạy lớn nhất của S1 và S2. Vũ Anh Dũng - Khoa CNTT 27 Một số trường hợp đệ quy „ Ví dụ, hàm sau đây thực ra chỉ là một vòng lặp đơn giản và là O(N ): long factorial(int n) { if (n <= 1 ) return 1; else return n * factorial(n 1); - } Vũ Anh Dũng - Khoa CNTT 28 Một số trường hợp đệ quy „ Ví dụ, hàm sau đây có độ phức tạp hàm mũ: long fib (int n) { 1 if(n <= 1) 2 return 1; else 3 return fib (n - 1) + fib (n - 2); } Gợi ý : T(n) = T(n-2) + T(n-1) + 2 fib( ) (3/2)n Vũ Anh Dũng - Khoa CNTT 29 n > Một số trường hợp đệ quy „ Ví dụ, hàm sau đây có độ phức tạp hàm mũ: fib(n) < (5/2)n „ Bằng cách tạo một mảng đơn giản và sử dụng vòng lặp, thời gian chạy có thể được rút ngắn một cách cơ bản. „ “Đừng tính bất cứ cái gì quá một lần” Vũ Anh Dũng - Khoa CNTT 30 Các thuật toán cho bài tổng dãy con lớn nhất „ Ví dụ trong file MaxSumTest.cpp „ Thuật toán 1 : 4 int maxSubSum1(const vector & a) 5 { 6 int maxSum = 0; 7 8 for (int i = 0; i < a.size(); i++) 9 for (int j = i; j < a size(); j++) . 10 { 11 int thisSum = 0; 12 13 for (int k = i; k < j); k++) 14 thisSum += a[k]; 15 16 if(thisSum > maxSum) 17 maxSum = thisSum; 18 } 19 20 return maxSum; Vũ Anh Dũng - Khoa CNTT 31 21 } Các thuật toán cho bài tổng dãy con lớn nhất – Thuật toán 1 „ Đánh giá thuật toán 1 „ Số bước tính toán : ∑ ∑ ∑− = − = = 1 0 1 1 N i N ij j ik „ Trước tiên ta có : ∑j 11 +−= = ij ik Vũ Anh Dũng - Khoa CNTT 32 Các thuật toán cho bài tổng dãy con lớn nhất – Thuật toán 1 „ Tiếp theo : ∑− = −+−=+− 1 2 ))(1()1( N ij iNiNij ∑∑ = − = +−+−=−+− N i N i iNiNiNiN 1 1 0 2 )2)(1( 2 ))(1( 131 NNN 2 23 2 )1() 2 3( 6 )12)(1( 2 1 1)23( 2 ) 2 ( 2 2 1 2 11 2 NNNNNNNNN NNiNi iii +++++−++= ++++−= ∑∑∑ === „ Độ phức tạp tính toán cho thuật toán 1 : O(N 3) 6 23 23 NNN ++= Vũ Anh Dũng - Khoa CNTT 33 Các thuật toán cho bài tổng dãy con lớn nhất – Thuật toán 2 „ Chúng ta đưa ra cải tiến thuật toán 1 bằng cách loại bỏ 1 vòng lặp for và độ phức tạp chỉ còn O(N 2) „ Thuật toán 2 : 4 int maxSubSum2(const vector & a) 5 { 6 int maxSum = 0; 7 8 for( int i = 0; i < a.size( ); i++ ) 9 { 10 int thisSum = 0; 11 for( int j = i; j < a.size( ); j++ ) 12 { 13 thisSum += a[ j ]; 14 15 if( thisSum > maxSum ) 16 maxSum = thisSum; 17 } 18 } Vũ Anh Dũng - Khoa CNTT 34 19 20 return maxSum; 21 } Các thuật toán cho bài tổng dãy con lớn nhất – Thuật toán 3 „ Thuật toán 3 : Tổng lớn nhất các dãy con có thể ở một trong ba vị trí : „ Có thể trong nửa trái hay nửa phải của đầu vào, hoặc nằm ở giữa, thuộc về cả hai nửa. ầ ể ằ„ Hai trường hợp đ u có th giải được b ng đệ quy. „ Trường hợp cuối, tìm tổng lớn nhất trong nửa đầu bao gồm cả phần tử cuối cùng của nửa đầu và tìm tổng lớn nhất , trong nửa cuối bao gồm cả phần tử đầu tiên trong nửa cuối. Hai tổng này được cộng với nhau. Vũ Anh Dũng - Khoa CNTT 35 Các thuật toán cho bài tổng dãy con lớn nhất – Thuật toán 3 „ Thuật toán 3 : 6 int maxSumRec( const vector & a, int left, int right ) 7 { 8 if( left == right ) // Base case 9 if( a[left] > 0 ) 10 return a[left]; 11 else 12 return 0; 13 14 int center = ( left + right ) / 2; 15 int maxLeftSum = maxSumRec( a, left, center ); 16 int maxRightSum = maxSumRec( a, center + 1, right ); 17 18 int maxLeftBorderSum = 0, leftBorderSum = 0; 19 for( int i = center; i >= left; i-- ) 20 { 21 leftBorderSum += a[ i ]; Vũ Anh Dũng - Khoa CNTT 36 22 if( leftBorderSum > maxLeftBorderSum ) 23 maxLeftBorderSum = leftBorderSum; 24 } Các thuật toán cho bài tổng dãy con lớn nhất – Thuật toán 3 „ Thuật toán 3 : 25 26 int maxRightBorderSum = 0, rightBorderSum = 0; 27 for( int j = center + 1; j <= right; j++ ) 28 { 29 rightBorderSum += a[ j ]; 30 if( rightBorderSum > maxRightBorderSum ) 31 maxRightBorderSum = rightBorderSum; 32 } 33 34 return max3( maxLeftSum, maxRightSum, 35 maxLeftBorderSum + maxRightBorderSum ); 36 } 42 int maxSubSum3( const vector & a ) 43 { 44 return maxSumRec( a, 0, a.size( ) - 1 ); Vũ Anh Dũng - Khoa CNTT 37 45 } Các thuật toán cho bài tổng dãy con lớn nhất – Thuật toán 3 „ Đánh giá thuật toán 3 : „ T(1) = 1 „ T(N) = 2*T(N/2) + N „ T(1) = 1, T(2) = 2*1+2 = 2*2, T(4) = 2*4+4, T(8)= 2*12+8 = 8*4, T(16) = 32*2+16=16*5 „ Vậy nếu N=2k thì T(N) = N*(k+1)=NlogN+N „ T(N) = O(NlogN) Vũ Anh Dũng - Khoa CNTT 38 Các thuật toán cho bài tổng dãy con lớn nhất – Thuật toán 4 „ Có độ phức tạp tuyến tính O(N ) „ Thuật toán 4 : 4 int maxSubSum4( const vector & a ) 5 { 6 int maxSum = 0, thisSum = 0; 7 8 f ( i t j 0 j < i () j++ )or n = ; a.s ze ; 9 { 10 thisSum += a[ j ]; 11 12 if( thisSum > maxSum ) 13 maxSum = thisSum 14 else if( thisSum < 0 ) 15 thisSum = 0; 16 } 17 Vũ Anh Dũng - Khoa CNTT 39 18 return maxSum; 19 } Thuật toán Euclid „ Tìm ước số chung lớn nhất „ Định lý : Định lý 2.1. Nếu M > N, thì M mod N < M/2. „ Độ phức tạp tính toán : O(logN ) Vũ Anh Dũng - Khoa CNTT 40