Kĩ thuật lập trình - Chương 1: Các phương pháp phân tích thuật toán

*Chương 1:Các phương pháp phân tích thuật toánTrịnh Huy HoàngKhoa Công nghệ thông tinĐại học Sư phạm TPHCM*Nội dungMột số kiến thức Toán cần thiếtThuật toán là gì?Vai trò của phân tích thuật toánCác phương pháp phân tích thuật toánBộ khung cho quá trình phân tích thuật toánMã giảRAMThời gian thực hiện chương trìnhĐộ phức tạp của chương trình*Một số kỹ thuật Toán học thường dùngChứng minh qui nạpChứng minh mệnh đề đúng với trường hợp đầu tiên (n=n0)Giả sử mệnh đề đúng đến trường hợp thứ k (n=k)Chứng minh mệnh đề đúng với trường hợp thứ k+1 (n=k+1)Kết luận mệnh đề đúng với mọi trường hợp (mọi n >= n0)*Một số kỹ thuật Toán học thường dùng (tt)Các tổng dãy số thường dùngDãy số họcif |x| =1 số nguyên Output: Phần tử lớn nhất trong AcurrentMax ← A[1]for i ← 2 to n do if currentMax 20 thì T1 0d(n) = O(f(n)), e(n) = O(g(n))  d(n)+e(n) = O(f(n)+g(n))d(n) = O(f(n)), e(n) = O(g(n))  d(n)e(n) = O(f(n)g(n))d(n) = O(f(n)), f(n) = O(g(n))  d(n) = O(g(n))f(n) là một đa thức bậc d  f(n) = O(nd)nx=O(an),x>0, a>1lognx = O(logn), x>0*Phương pháp tính độ phức tạpChúng ta sẽ nói đến phương pháp tính độ phức tạp (thời gian thực hiện) của:Chương trình không gọi chương trình con.Chương trình có gọi chương trình con không đệ quy.Chương trình đệ quyTrước hết ta có hai quy tắc quan trọng là quy tắc cộng và quy tắc nhânQuy tắc cộng: Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n))).Quy tắc nhân: Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau là T(n) = O(f(n).g(n)). *Qui tắc tổng quát để phân tích một chương trình không có chương trình conThời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1)Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi các lệnh.Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1).Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. 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.*Ví dụ 1: Thủ tục sắp xếp “nổi bọt”void BubbleSort(int a[n]){ int i,j,temp;/*1*/ for(i= 0; i=i+1;j--)/*3*/ if (a[j].key 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à return tích số. Thời gian để thực hiện phép nhân và return là một hằng C2. Vậy ta có phương trình:*Giải phương trình đệ quyCó ba phương pháp giải phương trình đệ quy:Phương pháp truy hồi.Phương pháp đoán nghiệm.Lời giải tổng quát của một lớp các phương trình đệ quy.*Phương pháp truy hồiDùng đệ quy để thay thế bất kỳ T(m) với m 1 được thay thế bởi biểu thức của các T(1) hoặc T(0). Vì T(1) và T(0) luôn là hằng số nên chúng ta có công thức của T(n) chứa các số hạng chỉ liên quan đến n và các hằng số. Từ công thức đó ta suy ra nghiệm của phương trình. *Ví dụ 1 về giải phương trình đệ quy bằng phương pháp truy hồi 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) + 3C2 T(n) = T(n-i) + iC2Quá trình trên kết thúc khi n - i = 0 hay i = n. Khi đó ta có T(n) = T(0) + nC2 = C1 + nC2 = O(n)*Ví dụ 2 về giải phương trình đệ quy bằng phương pháp truy hồi ..Quá trình suy rộng sẽ kết thúc khi n/2i = 1 hay 2i = n và do đó i = logn. Khi đó ta có:T(n) = nT(1) + lognC2n = C1n + C2nlogn = O(nlogn). *Lời giải tổng quát cho một lớp các phương trình đệ quyTrong mục này, chúng ta sẽ nghiên cứu các phần sau:Bài toán đệ quy tổng quát.Thành lập phương trình đệ quy tổng quát.Giải phương trình đệ quy tổng quát.Các khái niệm về nghiệm thuần nhất, nghiệm riêng và hàm nhân.Nghiệm của phương trình đệ quy tổng quát khi d(n) là hàm nhân.Nghiệm của phương trình đệ quy tổng quát khi d(n) không phải là hàm nhân. *Bài toán đệ quy tổng quátÐể giải một bài toán kích thước n, ta chia bài toán đã cho thành a bài toán con, mỗi bài toán con có kích thước n/b. Giải các bài toán con này và tổng hợp kết quả lại để được kết quả của bài toán đã cho. Với các bài toán con chúng ta cũng sẽ áp dụng phương pháp đó để tiếp tục chia nhỏ ra nữa cho đến các bài toán con kích thước 1. Kĩ thuật này sẽ dẫn chúng ta đến một giải thuật đệ quy.Giả thiết rằng mỗi bài toán con kích thước 1 lấy một đơn vị thời gianGiả thiết thời gian để chia bài toán kích thước n thành các bài toán con kích thước n/b và tổng hợp kết quả từ các bài toán con để được lời giải của bài toán ban đầu là d(n). *Thành lập phương trình đệ quy tổng quátNếu gọi T(n) là thời gian để giải bài toán kích thước n Thì T(n/b) là thời gian để giải bài toán con kích thước n/b. Khi n = 1 theo giả thiết trên thì thời gian giải bài toán kích thước 1 là 1 đơn vị, tức là T(1) = 1. Khi n lớn hơn 1, ta phải giải đệ quy a bài toán con kích thước n/b, mỗi bài toán con tốn T(n/b) nên thời gian cho a lời giải đệ quy này là aT(n/b). Ngoài ra ta còn phải tốn thời gian để phân chia bài toán và tổng hợp các kết quả, thời gian này theo giả thiết trên là d(n). Vậy ta có phương trình đệ quy:*Giải phương trình đệ quy tổng quát........*Giải phương trình đệ quy tổng quát (tt) Giả sử n = bk, quá trình suy rộng trên sẽ kết thúc khi i = k. Khi đó ta được: Thay vào trên ta có:*Nghiệm thuần nhất và nghiệm riêngNghiệm thuần nhấtak = nlogba Nghiệm riêng Nghiệm của phương trình là: MAX(NTN,NR). *Hàm nhânMột hàm f(n) được gọi là hàm nhân (multiplicative function) nếu f(m.n) = f(m).f(n) với mọi số nguyên dương m và n.Ví dụ: Hàm f(n) = nk là một hàm nhân, vì f(m.n) = (m.n)k = mk.nk = f(m).f(n).Hàm f(n) = logn không phải là một hàm nhân, vì f(n.m) = log(n.m) = logn+logm  logn.logm = f(n).f(m) *Tính nghiệm riêng khi d(n) là hàm nhânKhi d(n) là hàm nhân, ta có: d(bk-j) = d(b.b.b..b) = d(b).d(b)d(b) = [d(b)]k-j *Ba trường hợpTrường hợp 1: a > d(b) Trong công thức trên ta có ak > [d(b)]k, theo quy tắc lấy độ phức tạp ta có NR là O(ak) = O(nlogba) = NTN. Do đó T(n) là O(nlogba).Trường hợp 2: a ak, theo quy tắc lấy độ phức tạp ta có NR là O([d(b)]k) = O(nlogbd(b)) > NTN. Do đó T(n) là O(nlogbd(b)). *Ba trường hợp (tt)Trường hợp 3: a = d(b) Công thức trên không xác đinh nên ta phải tính trực tiếp nghiệm riêng:Do n = bk nên k = logbn và ak = nlogba. Vậy NR là nlogbalogbn > NTN. Do đó T(n) là O(nlogbalogbn).*Ví dụ: GPT với T(1) = 1 vàPhương trình đã cho 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(nlogbd(b)) = O(nlog8) = O(n3). *Nghiệm của phương trình đệ quy tổng quát khi d(n) không phải là hàm nhânTrong trường hợp hàm tiến triển không phải là một hàm nhân thì chúng ta không thể áp dụng các công thức ứng với ba trường hợp nói trên mà chúng ta phải tính trực tiếp NR, sau đó lấy MAX(NR,NTN).*Ví dụ: GPT 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 = nDo 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*Ví dụ (tt)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 2k = n và k = logn, NR= O(nlog2n) > NTNT(n) = O(nlog2n).*Vd: GPT với T(1) = 1 vàPhương trình đã cho 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(nlogbalogbn) = O(nlog1logn) = O(logn). *Vd: GPT với T(1) = 1 vàPhương trình đã cho có dạng phương trình 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.**Bài tậpXét thuật toán tìm phần tử có giá trị x trong một mảng A cho trước.Viết mã giả mô tả thuật toán trênĐếm số thao tác cơ sở trong thuật toán trênXác định độ phức tạp thuật toánXét thuật toán tìm phần tử có giá trị x trong một ma trận A có kích thước mxn cho trước.Viết mã giả mô tả thuật toán trênĐếm số thao tác cơ sở trong thuật toán trênXác định độ phức tạp thuật toán*Ví dụ minh họaPhát biểu bài toán:Cho trước một mảng X chứa n số cho trước, mảng trung bình tiền tố A của mảng X là một mảng có n phần tử được định nghĩa như sau:A[i] = avg(X[1]..X[i])Hãy viết thuật toán xác định mảng trung bình tiền tố A của mảng X cho trước.*Thuật toán 1:Algorithm prefixAverages1(X) Input: Một mảng n phần tử số X Output: một mảng n phần tử A thỏa A[i] là trung bình cộng của các phần tử X[1],X[i]. For i ← 1 to n do a ← 0 For j ← 1 to i do a ← a + X[i] A[i] ← a / i Return array A *Phân tích thuật toán 1*Phân tích thuật toán 1 (tt)Câu lệnh trả về:Return: Truy xuất phần tử mảng: Tổng cộng: thời gian thực thi của thuật toánT(n) =?*Thuật toán 2Lưu ý rằng: đặt S[i] = Sum(X[1]..X[i])  A[i] = S[i] / iAlgorithm prefixAverages2(X) Input: Một mảng n phần tử số X Output: một mảng n phần tử A thỏa A[i] là trung bình cộng của các phần tử X[1],X[i]. s ← 0 For i ← 1 to n do s ← s + X[i] A[i] ← s / i Return array A*Phân tích thuật toán 2*Bài tậpCài đặt hai thuật toán 1 và 2 bằng ngôn ngữ C/C++.Khảo sát thời gian thực thi hai thuật toán lần lượt với các giá trị n khác nhauThời gian thực thi của hai thuật toán với cùng một giá trị n (rất lớn, >10000) có khác nhau hay không? Nếu có giải thích vì sao có. Nếu không giải thích vì sao không.Vẽ đồ thị thể hiện thời gian thực thi của mỗi thuật toán phụ thuộc vào n.