Bài giảng Phân tích và thiết kế giải thuật (Analys And Design Algorithms) - Chương 1: Các khái niệm căn bản về phân tích độ phức tạp giải thuật

1PHÂN TÍCH VÀ  THIẾT KẾ GIẢI THUẬTANALYS AND DESIGN ALGORITHMS12Mục tiêu môn học Cung cấp kiến thức và kỹ năng trong việc phân tích độ phức tạp tính toán của giải thuật. Tìm hiểu các chiến thuật thiết kế giải thuật23Nội dung môn học3TTNội dungSố tiếtPhân bổ thời gianGhi chúLý thuyếtBài TậpTự học1Các khái niệm căn bản về phân tích độ phức tạp giải thuật660102Phân tích độ phức tạp của một số giải thuật sắp thứ tự và tìm kiếm883203Phân tích độ phức tạp của một số giải thuật trên cấu trúc dữ liệu993204Phân tích độ phức tạp của một số giải thuật đồ thị553205Các chiến lược thiết kế giải thuật883156Vấn đề NP-đầy đủ99320TỔNG606001054Đánh giá kết quảKiểm tra giữa kỳ: Tự luậnĐiểm Kiểm tra giữa kỳ n thì sang B7, ngược lại sang B4B4: S=S+iB5: i=i+2B6: Quay lại B3B7: Tổng cần tìm là S1314Các đặc trưng của Thuật toánINPUT: Có các bộ dữ liệu đầu vào thuộc một tập hợp dữ liệu nào đó. OUTPUT: Xuất dữ liệu đầu ra theo yêu cầu của bài toánTính xác định: Mỗi bước của thuật toán hoàn toàn xác định, được mô tả chính xác và cho kết quả xác địnhTính dừng: Thuật toán phải kết thúc sau hữu hạn bước.Tính phổ dụng: Thuật toán áp dụng được cho mọi bộ dữ liệu đầu vào thuộc tập hợp dữ liệu1415Mối quan hệ của CTDL và thuật toánCTDL + Thuật toán = Chương trình1516Các phương pháp biểu diễn giải thuậtDiễn đạt bằng ngôn ngữ tự nhiênBiểu diễn bằng sơ đồ khốiBiểu diễn bằng Giả mã, thông thường dùng ngôn ngữ tựa PASCAL; Ngôn ngữ lập trình cấp cao (High programming languages) như Pascal, C/C++ vv 1617Các phương pháp biểu diễn giải thuậtVí dụ: Tìm x trong dãy a1, a2, ...., an Đầu vào: Số x, dãy n số a1, a2, ..., anĐầu ra: Một giá trị logic true hoặc falseSearch(x, a, n)1 for i ←1 to n 2 do if ai= x then return true4 return false1718Cấu trúc dữ liệuThuật toánĐộ phức tạp của thuật toán (algorithm complexity)18Thuật ngữ và khái niệm19Độ phức tạp của thuật toánĐộ phức tạp của giải thuật là chi phí về tài nguyên của hệ thống (chủ yếu là thời gian, bộ nhớ, CPU, đường truyền) cần thiết để thực hiện giải thuậtPhân tích giải thuật (Analyzing of Algorithm) là quá trình tìm ra những đánh giá về tài nguyên cần thiết để thực hiện giải thuật1920Thời gian thực hiện thuật toánĐộ phức tạp về thời gian của giải thuật:Được qui về đếm số lệnh cần thực thi của giải thuậtĐó là một hàm T(n) phụ thuộc vào kích thước n của inputCoi như có một máy trừu tượng (abstract machine) để thực hiện giải thuật2021Thời gian tối thiểu để thực hiện giải thuật với mọi kích thước đầu vào n gọi là thời gian chạy tốt nhất(best-case)của giải thuậtThời gian nhiều nhất để thực hiện giải thuật với mọi kích thước đầu vào n được gọi là thời gian chạy xấu nhất (worst-case) của giải thuậtThời gian trung bình để thực hiện giải thuật với mọi kích thước đầu vào n được gọi là thời gian chạy trung bình (average case) của giải thuật21Độ phức tạp thời gian của thuật toán22Ví dụ Đánh giá độ phức tạp về thời gian của giải thuậtSearch(x, a, n)1 for i ←1 to n 2 do if ai= x 3 then return true4 return false22Độ phức tạp thời gian của thuật toán23Giải:Gọi α, β và γ là thời gian thực hiện của phép gán, phép so sánh và trả về của giải thuậtTrường hợp tốt nhất: Nếu a1= x, thìT(n) = α+β+ γTrường hợp xấu nhất : Nếu x ∉{a1, a2, ..., an} thì T(n) = (n+1)α+ nβ+ γ23Độ phức tạp thời gian của thuật toán24Giải:Trường hợp trung bình: Tồn tại i, ai = x, thìT(n) = f(i) = iα+ iβ+ γ với xác suất p(i) = 1/nT(n) = [(α+β+ γ)+ (2α+ 2β+ γ)+...+(nα+ nβ+ γ)]/n = [(n(n+1)(α+β)/2 +nγ]/n = (n+1)(α+β)/2 + γLưu ý: T(n) là kỳ vọng (expected value) của f(i)=αi +βi +γ trên không gian xác suất {1, 2, , n} 24Độ phức tạp thời gian của thuật toán25Khung thức của sự phân tíchBước 1: Đặc trưng hóa dữ liệu nhập và quyết định kiểu phân tích thích hợp. Thông thường, ta tập trung vào việcChứng minh rằng thời gian tính toán luôn nhỏ hơn một “cận trên” (upper bound), hay Dẫn xuất ra thời gian chạy trung bình đối với một dữ liệu nhập ngẫu nhiên. Bước 2: nhận dạng thao tác trừu tượng (abstract operation) mà giải thuật dựa vào đó làm việc. Thí dụ: thao tác so sánh trong giải thuật sắp thứ tự. Tổng số thao tác trừu tượng thường tùy thuộc vào một vài đại lượng.  Bước 3: thực hiện phân tích toán học để tìm ra các giá trị trung bình và giá trị xấu nhất của các đại lượng quan trọng.26Hai trường hợp phân tíchThường thì không khó để tìm ra cận trên của thời gian tính toán của một giải thuật.Nhưng phân tích trường hợp trung bình thường đòi hỏi một sự phân tích toán học cầu kỳ, phức tạp.Về nguyên tắc, một giải thuật có thể được phân tích đến một mức độ chính xác rất chi li. Nhưng trong thực tế, chúng ta thường chỉ tính ước lượng (estimating) mà thôiTóm lại, chúng ta tìm kiếm một ước lượng thô về thời gian tính toán của một giải thuật (nhằm mục đích phân lớp độ phức tạp).27Phân lớp độ phức tạpHầu hết các giải thuật thường có một thông số chính, N, số mẫu dữ liệu nhập mà được xử lý. Thí dụ:Kích thước của mảng (array) được sắp thứ tự hoặc tìm kiếm. Số nút của một đồ thị.Giải thuật có thể có thời gian tính toán tỉ lệ với 1. Nếu tác vụ chính được thực thi một vài lần. thời gian tính toán là hằng số.2. lgN (logarithmic) log2N  lgNGiải thuật tăng chậm hơn sự tăng của N.28 Các ký hiệu tiệm cậnCác kí hiệu tiệm cận nhằm đánh giá độ lớn của các hàm T(n) khi n   theo các hàm f(n) đơn giản hơnKí hiệu “O lớn” O(f(n))Kí hiệu “omega” (f(n))Kí hiệu “theta” (f(n))2829Kí hiệu “O lớn”Hàm T(n)=f(n) được gọi là O(g(n)) nếu tồn tại no và hằng số C sao cho : với mọi n >= n0 T(n) no ta có T(n) > C.g(n) Viết T(n) = (g(n)) hay T(n)  (g(n))Ý nghĩa : Mức tăng của T(n) không kém mức tăng của g(n)Ký hiệu Ω biểu diễn g(n) là một chặn dưới tiệm cận (asymptotic lower bound) của f(n)3031Kí hiệu theta (f(n))T(n)=f(n) được gọi là theta của g(n) nếu tồn tại số tự nhiên no và các hằng số C1 , C2 sao cho: n>no ta có C1g(n) =1: T(n)  3n.log3n.Dùng công thức đổi cơ số log3n = log2n / log23 ta có T(n)  (3/log23) n log2nVí dụ: Xét hàm T(n) = 3n.log3n+234Định lý:Cho hai hàm f(n) và g(n), ta có f(n) = Θ(g(n)) khi và chỉ khi f(n) = O(g(n)) và f(n) = Ω(g(n)).35TỔNG QUÁTMọi đa thức P(n) bậc k khi n  tương đương với nkPk(n) = aknk+...+ ao=  (nk)3536Luật tổngGiả sử thuật toán gồm hai phần (hoặc nhiều phần), thời gian chạy của phần đầu là T1(n), phần sau là T2(n). Khi đó thời gian chạy của thuật toán là T1(n) + T2(n) sẽ được suy ra từ sự đánh giá của T1(n) và T2(n) theo luật sau:3637Luật tổngGiả sử T1(n) = O(f(n)) và T2(n) = O(g(n)). Nếu hàm f(n) tăng nhanh hơn hàm g(n), tức là g(n) = O(f(n)), thì T1(n) + T2(n) = O(f(n)).Vắn tắt O(T1(n) + T2(n))=max(T1(n) ,T2(n))3738Luật tổng - TíchNếu T1(n) = O(f(n)) vàT2(n) = O(g(n)) thìT1(n)+T2(n) = O(max(f(n), g(n))T1(n).T2(n) = O(f(n).g(n))c.O(f(n)) = O(f(n))O(c) ≡O(1)Lưu ý: Các tính chất trên cũng đúng cho Θ và ΩBậc của thời gian chạy càng lớn thì giải thuật càng chậm (chẳng hạn, giải thuật có thời gian chạy T(n) = O(n2) sẽ hiệu quả hơn giải thuật có thời gian chạy T(n) = O(n3)3839Thời gian chạy của các lệnhThời gian thực hiện các phép toán sơ cấp là O(1).Lệnh gán có dạng X = Thời gian chạy của lệnh gán là thời gian thực hiện biểu thức3940 2. Lệnh lựa chọnLệnh lựa chọn if-else có dạng if () lệnh 1 else lệnh 2Giả sử thời gian đánh giá điều kiện là T0(n), thời gian thực hiện lệnh 1 là T1(n), thời gian thực hiện lệnh 2 là T2(n). Thời gian thực hiện lệnh lựa chọn if-else sẽ là thời gian lớn nhất trong các thời gian T0(n) + T1(n) và T0(n) + T1(n).40413. Lệnh lặp: for, while, do-whileGiả sử :Số tối đa các lần lặp là L(n). Thời gian kiểm tra điều kiện lặp là T0(n).Thời gian thực hiện lệnh lặp ở lần i (i=1,2,..., L(n)) là Ti(n). Như vậy thời gian chạy của lệnh lặp là:4142Ví dụBước 1. Gán Tổng = 0. Gán i = 0.Bước 2. – Tăng i thêm 1 đơn vị. – Gán Tổng = Tổng + iBước 3. So sánh i với n – Nếu i max then max := A[i] endNếu C(n) là độ phức tạp tính toán của giải thuật được tính theo thao tác so sánh (A[i]> max). Hãy xác định C(n) trong trường hợp xấu nhất.3. Lệnh lặp: for, while, do-while44Thao tác căn bản của thủ tục MAX là thao tác so sánh.Tổng số thao tác so sánh của thủ tục MAX chính là số lần thân vòng lặp được thực thi: (n-1).Vậy độ phức tạp tính toán của giải thuật là O(n).Đây là độ phức tạp của cả hai trường hợp trung bình và xấu nhất.Ghi chú: Nếu thao tác căn bản là phát biểu gán (max := A[i]) thì O(n) là độ phức tạp trong trường hợp xấu nhất.3. Lệnh lặp: for, while, do-while45Thí dụ 2: Giải thuật kiểm tra xem có phải mọi phần tử trong mảng 1 chiều là khác biệt nhau.function UniqueElements(A, n)begin for i:= 1 to n –1 do for j:= i + 1 to n do if A[i] = A[j] return false return trueendTrong trường hợp xấu nhất, mảng không hề có hai phần tử nào bằng nhau hoặc mảng có hai phần tử cuối cùng bằng nhau. Lúc đó một sự so sánh diễn ra mỗi khi thân vòng lặp trong được thực hiện.3. Lệnh lặp: for, while, do-whilei = 1 j chạy từ 2 cho đến n  n – 1 lần ssi = 2 j chạy từ 3 cho đến n  n – 2 lần ss . .i = n -2 j chạy từ n-1 cho đến n 2 lần ssi = n -1 j chạy từ n cho đến n 1 lần ssTóm lại, tổng số lần so sánh là:1 + 2 + 3 + + (n-2) + (n-1) = n(n-1)/2Vậy độ phức tạp tính toán của giải thuật trong trường hợp xấu nhất là O(n2).46Ví dụ Thuật toán tạo ra ma trận đơn vị A cấp n;(1) for i: = 1 to n do (2) for j: = 1 to n do (3) A[ i,j]: = 0;(4) for i: = 1 to n do(5) A[i,i] := 1;46Lệnh lặp for (1) có thân lại là một lệnh lặp for (2). Số lần lặp của lệnh for (2) là n, thân của nó là lệnh (3) có thời gian chạy là O(1), do đó thời gian chạy của lệnh lặp for này là O(n). Lệnh lặp for (1) cũng có số lần lặp là n, thân của nó có thời gian đã đánh giá là O(n), nên thời gian của lệnh lặp for (1) là O(n2). Tương tự lệnh for (4) có thời gian chạy là O(n). Sử dụng luật tổng, ta suy ra thời gian chạy của thuật toán là O(n2).47Các độ phức tạp thường gặpĐộ phức tạp hằng số: O(1) – thời gian chạy không phụ thuộc vào độ lớn đầu vàoĐộ phức tạp tuyến tính: O(n) – thời gian chạy tỉ lệ thuận với độ lớn đầu vàoĐộ phức tạp logarit: O(logn)Độ phức tạp đa thức: O(P(n)), với P là đa thức có bậc từ 2 trở lênĐộ phức tạp hàm mũ: O(2n)4748Bảng so sánh các độ phức tạp của thuật toánMột số lớp thuật toán4849Thứ tự độ phức tạp của thuật toán4950Nguyên tắc phân tích độ phức tạp trung bìnhĐể tính độ phức tạp trung bình của một giải thuật A, ta phải làm một số bước: Quyết định một không gian lấy mẫu (sampling space) để diễn tả những dữ liệu đầu vào (kích thước n) có thể có. Giả sử không gian lấy mẫu là S = { I1, I2,, Ik} 2. Ta phải định nghĩa một phân bố xác xuất p trên S mà biểu diễn mức độ chắc chắn mà dữ liệu đầu vào đó có thể xảy ra. 3. Ta phải tính tổng số tác vụ căn bản được giải thuật A thực hiện để xử lý một trường hợp mẫu. Ta dùng v(Ik) ký hiệu tổng số tác vụ được thực hiện bởi A khi dữ liệu đầu vào thuộc trường hợp Ik. 51Phân tích độ phức tạp trung bình (tt.)4. Ta tính trị trung bình của số tác vụ căn bản bằng cách tính kỳ vọng sau: Cavg(n) = v(I1).p(I1) + v(I2).p(I2) + +v(Ik).p(Ik).Thí dụ: Cho một mảng A có n phần tử. Tìm kiếm vị trí mà trị X xuất hiệntrong mảng A. begin i := 1; while i A[i] do i := i+1;endGiả sử X có xuất hiện trong mảng và giả định rằng xác xuất để nó xuất hiện tại một vị trí bất kỳ trong mảng là đều nhau và xác xuất để mỗi trường hợp xảy ra là p = 1/n. Số lần so sánh để tìm thấy X nếu nó xuất hiện tại vị trí 1 là 1Số lần so sánh để tìm thấy X nếu nó xuất hiện tại vị trí 2 là 2Số lần so sánh để tìm thấy X nếu nó xuất hiện tại vị trí n là n Tổng số tác vụ so sánh trung bình là: C(n) = 1.(1/n) + 2.(1/n) + + N.(1/n) = (1 + 2 + + n).(1/n) = (1+2++n)/n = n(n+1)/2.(1/n) = (n+1)/2.52Chia để trị - Divide and conquer algorithm Khái niệm chia để trịĐệ quy và hệ thức truy hồiPhân tích giải thuật đệ quyChiến lược thiết kế giải thuậtThiết kế giải thuật kiểu “trực tiếp” (bruce-force)53Khái niệm Chia để trịSơ đồ chungVí dụ đơn giảnCác giải thuật đã biếtMột số bài toán khác54Sơ đồ chungChia để trị là một kỹ thuật thiết kế thuật toán bao gồm: Chia một bài toán cần giải ra thành những bài toán con nhỏ hơn có cùng một loại vấn đềGiải từng bài toán con đó một cách lần lượt và độc lập Tổng hợp các lời giải con thu được thành lời giải của bài toán ban đầu. Chia để trị thường dẫn đến giải thuật đệ quy5455SƠ ĐỒ TỔNG QUÁTCHIATRỊTỔNG HỢP5556bài toán kích thước nbài toán con 1kích thước n/2bài toán con 2kích thước n/2lời giải cho bài toán con 1lời giải cho bài toán con 2lời giải cho bài toán ban đầuChiến lược chia-để-trịCHIATRỊTỔNG HỢP57Chú ýKhi thực hiện CHIA ĐỂ TRỊ thường dẫn đến giải thuật đệ quy.Một giải thuật đệ quy thường gồm hai phần:Cơ sở của đệ quy: Các trường hợp cơ bản (thường với kích thước nhỏ) có thể giải trực tiếp;Phần đệ quy: Tổng hợp lời giải: tìm lời giải của bài toán lớn từ các lời giải của các bài toán nhỏ 5758Ví dụ đơn giảnBài Toán: Tìm phần tử lớn nhất trong một dãy số INPUT: Dãy không rỗng L[1..n] các số . OUTPUT: Số lớn nhất trong dãy L.Procedure LargestNumber {Chia để tri} if n = 1 then return L[1] else begin m:= int(n/2); largest1:= LargestNumber(L[1..m]) largest2:=LargestNumber(L[m+1..n]) if largest1 > largest2 then largest:= largest1 else largest:= largest2 return largest end;5859Ví dụ 2: Cặp điểm gần nhấtBài toánCho dãy n điểm trên mặt phẳng với các toa độ cho bởi mảng 2 chiều C : array [1...n, 2] of Integer trong đó Ai =(x,y) với ( x=C[i,1], y=C[i,2]) Tìm cặp điểm gần nhất trong chúng.5960Phân tích các giai đoạnBài toán con cơ bản: Với n đủ nhỏ có thể so sánh trực tiếpCHIAChia tập n điểm thành hai phần bằng đường thẳng song song với Oy6061TRỊ : Giải các bài toán conBài toán con 1 Tìm cặp điểm gần nhất trong nửa trái Bài toán con 2Tìm cặp điểm gần nhất trong nửa phảiBài toán con 3Tìm cặp điểm gần nhất trong dải nằm gần đường phân cách6162TỔNG HỢP LỜI GIẢIQuá trình giải bài toán con 2, 3 kết hợp với quá trình tổng hợp lời giải:1. Khi giải Bài toán 1, lưu kết quả gồm:Hai điểm P,Q gần nhau nhấtGiá trị dmin của khoảng cách ngắn nhất2. Khi giải bài toán con 2 và 3: Chỉ xét các cặp điểm có hiệu hoành độ và hiệu tung độ nhỏ hơn dmin.6263Kỹ thuật CHIASắp xếp các điểm theo chiều tăng của hoành độ (x1 , y1), (x2 , y2), ..., (xn , yn) với x1  x2  ....  xn Lấy m = Int (n/2)Nửa trái gồm các điểm  (x1 , y1), (x2 , y2), ..., (xm , ym)Nửa phải gồm các điểm (xm+1 , ym+1), , ..., (xn , yn)6364Kỹ thuật TRỊKỹ thuật chung: Lưu cặp điểm gần nhất vào hai biến cp1, cp2 và khoảng cách giữa chúng vào biến dmin , sau đó chỉ cần kiểm tra cặp điểm có hiệu hoành độ nhỏ hơn dmin bằng thủ tục Check sau đâyProcedure Check(p1,p2:Point);Begin dx=Abs(p1.x-p2.x); If dx> dmin then exit; dy=Abs(p1.y-p2.y); If dy> dmin then exit; d:=sqrt(dx*dx+dy*dy) ; if d 0 và n ≥ n0Giả thuyết qui nạp: T(k) ≤ d g(k) với mọi k 0. 99Phương pháp cây đệ quy (recursion tree)100Ví dụ 1W(n) = 2W(n/2) + n2101Ví dụ 2E.g.: T(n) = 3T(n/4) + cn2102Ví dụ 3W(n) = W(n/3) + W(2n/3) + O(n)Cung cấp cách thức giải các phương trình hồi quy có dạngVới a ≥ 1và b > 1 là các hằng số , f (n) là hàm dương tiệm cận. 103Phương pháp masterĐịnh lý master104Định lý có 3 trường hợp. Để xác định hàm f(n) thuộc trường hợp nào, cần so sánh giá trị của f(n) và (theo kiểu đa thức)Nếu f(n)  áp dụng case 3Nếu f(n) =  áp dụng case 2105Định lý masterVí dụ 1106Ví dụ 2107108Ví dụ 3Ba case trong định lý không thể bao phủ hết mọi khả năng của hàm f(n).Khi f(n) nhỏ hơn nhưng không nhỏ hơn theo kiểu đa thức (polynomially smaller) (f(n) nằm khoảng giữa case 1 và 2)Khi f(n) lớn hơn nhưng không lớn hơn theo kiểu đa thức (polynomially larger) (f(n) năm khoảng giữa case 2 và 3) Không thể áp dụng định lý master để giải phương trình hồi quy (recurrence).Nhược điểm của định lý master109Xét T (n) = 2T (n/2) + n lg nTa có: Có vẽ như f(n) lớn hơn (case 3)Nhưng thực tế f(n) không lớn hơn theo kiểu đa thức Không lớn hơn với bất kỳ   không thể áp dụng định lý master110Ví dụ 4111Chiến lược thiết kế giải thuật Một chiến lược thiết kế giải thuật (Algorithm Design Strategy) là một cách tiếp cận tổng quát để giải quyết vấn đề bằng giải thuật mà có thể áp dụng cho nhiều bài toán khác nhau trong nhiều lãnh vực khác nhau.Việc học những chiến lược thiết kế này hết sức quan trọng vì những lý do sau:Chúng cung cấp những chỉ dẫn để thiết kế giải thuật cho những bài toán mới.Giải thuật đóng một vai trò quan trọng trong khoa học máy tính. Dựa vào các chiến lược thiết kế giải thuật, ta có thể phân loại giải thuật dựa vào ý tưởng thiết kế nền tảng của chúng.112Chiến lược thiết kế giải thuật (tt.)“Chia-để-trị” là một ví dụ điển hình của một chiến lược thiết kế giải thuật.Ngoài ra còn có nhiều chiến lược thiết kế giải thuật nổi tiếng khácTập hợp những chiến lược thiết kế giải thuật tạo thành một bộ công cụ rất mạnh có sẵn giúp chúng ta nghiên cứu và xây dựng giải thuật.113Vài chuỗi số thông dụng Có một vài chuỗi số thông dụng trong việc phân tích độ phức tạp giải thuật. Chuỗi số cộngS1 = 1 + 2 + 3 + + nS1 = n(n+1)/2  n2/2S2 = 1 + 22 + 32 + + n2S2 = n(n+1)(2n+1)/6  n3/3 Chuỗi số nhânS = 1 + a + a2 + a3 + + anS = (an+1 -1)/(a-1)If 01, n/b nguyên, f(n) là một hàm, khi đóNếu f(n)=O(nlogba-ε) với một hằng ε>0 thìT(n)=Θ(nlogba)Nếu f(n)= Θ(nlogba), thìT(n)=Θ(nlogbalgn)Nếu f(n)=Ω(nlogba+ε) với một hằng ε>0 và af(n/b) ≤cf(n) với hằng c 14 then returnn*Factorial(n-1)124125Đọc và tìm hiểu thêmĐọc chương 1, 2, 3, 4 sách Introduction to Algorithmscủa Thomas H. Cormen, Charles E. Leiserson, Ronald D. Rivest. Introduction to Algorithms