[Giáo Trình] Phân Tích Thiết Kế Thuật Toán Và đánh Giá độ Phức Tạp Của ...

Tải bản đầy đủ (.pdf) (96 trang)

1. Trang chủ
>>
2. Công Nghệ Thông Tin
>>
3. Kỹ thuật lập trình

[Giáo trình] Phân tích thiết kế thuật toán và đánh giá độ phức tạp của giải thuật - ĐH Sư phạm Hà Nội

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.82 MB, 96 trang )

ĐẠI HỌC SƯ PHẠM HÀ NỘI NGUYỄN CHÍ TRUNG NGUYỄN THỊ THU THỦY PHÂN TÍCH THIẾT KẾ THUẬT TOÁN VÀ ĐÁNH GIÁ ĐỘ PHỨC TẠP GIẢI THUẬT HÀ NỘI 2010 Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 2 MỤC LỤC TÀI LIỆU THAM KHẢO 4 Chương 1. CÁC KHÁI NIỆM CƠ BẢN 5 1. Thuật toán (giải thuật, thuật giải) 5 1.1. Định nghĩa 5 1.2. Các đặc trưng của thuật toán 5 2. Phân tích thuật toán 5 2.1. Tại sao phải phân tích thuật toán 10 2.2. Thời gian thực hiện thuật toán 11 2.3. Khái niệm độ ph1độ phức tạp thuật toán 15 3.1. Qui tắc hằng số 15 3.2. Qui tắc cộng 16 3.3. Qui tắc lấy max 16 3.4. Qui tắc nhân 17 3. Các kỹ thuật đánh giá độ phức tạp thuật toán 17 3.1. Câu lệnh đơn 17 3.2. Câu lệnh hợp thành 17 3.3. Câu lệnh lặp với số lần lặp biết trước for-do 18 3.4. Câu lệnh rẽ nhánh if 19 3.5. Câu lệnh lặp với số lần lặp chưa biết trước while, repeat 19 4. Một số ví dụ minh họa thiết kế thuật toán và đánh giá độ phức tạp 21 Bài toán 1.1. Tính giá trị gần đúng của exp(x) theo khai triển Taylor 21 Bài toán 1.2 Thuật toán tìm kiếm tuần tự 22 Bài toán 1.3 Thuật toán tìm kiếm nhị phân 22 Bài toán 1.4 Thuật toán sắp xếp chọn lựa 23 5. Phân tích chương trình (con) đệ qui 24 5.1. Khái niệm về đệ qui 24 5.2. Chương trình (con) đệ qui 25 5.3. Xây dựng phương trình (công thức) đệ qui 25 5.4. Giải phương trình đệ qui và Định lí Thợ 26 BÀI TẬP CHƯƠNG 1 30 Chương 2 CHIA ĐỂ TRỊ 33 1. Sơ đồ chung của thuật toán chia để trị 33 1.1. Thuật toán β 33 1.2. Thuật toán γ 34 1.3. Thuật toán γ tổng quát 35 2. Một số ví dụ minh họa Chia để trị 35 2.1. Thuật toán sắp xếp trộn (Merge Sort) 35 2.2. Thuật toán sắp xếp nhanh (QuickSort) 37 2.3. Nhân số nguyên lớn 39 2.4. Mảng con trọng số lớn nhất 40 BÀI TẬP CHƯƠNG 2 43 Chương 3. QUY HOẠCH ĐỘNG 45 1. Giới thiệu phương pháp qui hoạch động 45 2. Phương pháp chung của qui hoạch động 45 3. Một số ví dụ minh họa 46 3.1. Dãy con tăng dần dài nhất 46 Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 3 3.2. Trở lại bài toán mảng con trọng số lớn nhất 51 3.3. Xâu con chung dài nhất 52 3.4. Bài toán cái túi 55 3.5. Nhân ma trận 57 BÀI TẬP CHƯƠNG 3 62 Chương 4. THUẬT TOÁN THAM LAM 64 1. Giới thiệu thuật toán tham lam 64 1.1. Đặc điểm của thuật toán tham lam 64 1.2. Sơ đồ chung của thuật toán tham lam 65 1.3. Chứng minh thuật toán đúng 65 2. Một số ví dụ minh họa 66 2.1. Bài toán tập các đoạn thẳng không giao nhau 66 2.2. Tìm hiểu các thuật toán tham lam đối với bài toán cái túi 69 2.3. Bài toán người du lịch (TSP - Travelling Salesman Problem) 70 2.4. Bài toán mã hóa Huffman 71 BÀI TẬP CHƯƠNG 4 75 Chương 5. CÁC THUẬT TOÁN ĐỒ THỊ CƠ BẢN 77 1. Các khái niệm cơ bản 77 1.1. Đồ thị 77 1.2. Các khái niệm 77 2. Các phương pháp biểu diễn đồ thị 78 1.1. Biểu diễn đồ thị bằng ma trận kề 78 1.2. Biểu diễn đồ thị bằng danh sách cạnh 78 1.3. Biểu diễn đồ thị bằng danh sách kề 79 1.4. Biểu diễn đồ thị bằng danh sách liên thuộc 81 3. Thuật toán tìm kiếm theo chiều rộng 81 3.1. Nguyên tắc tô màu 81 2.2. Breadth – First Tree 81 3.3. Mô tả thuật toán 82 4. Thuật toán tìm kiếm theo chiều sâu 84 4.1. Giới thiệu thuật toán 84 4.2. Thủ tục tìm kiếm theo chiều sâu 85 4.3. Đánh giá độ phức tạp thuật toán DFS và DFS-Visit 86 5. Bài toán tìm đường đi ngắn nhất 87 5.1. Một số khái niệm cơ bản 87 5.2. Thuật toán Dijkstra 88 6. Bài toán về cây khung nhỏ nhất 90 6.1. Các khái niệm cơ bản 90 6.2. Thuật toán Kruskal 91 6.3. Thuật toán Prim 92 BÀI TẬP CHƯƠNG 5 94 CÁC CHUYÊN ĐỀ MÔN HỌC 96 Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 4 TÀI LIỆU THAM KHẢO 1. Vũ Đình Hòa, “Giải thuật và đánh giá độ phức tạp giải thuật”, Gói giáo trình môn học theo chuẩn SCORM, Trường ĐHSP HN. 2. Hồ Sỹ Đàm (chủ biên), Đỗ Đức Đông, Lê Minh Hoàng, Nguyễn Thanh Hùng, “Tài liệu giáo khoa Chuyên Tin” Quyển 1 và 2, Nhà xuất bản giáo dục, 2009. 3. Nguyễn Đức Nghĩa, Nguyễn Tô Thành, “Toán rời rạc”, Nhà xuất bản giáo dục, tài bản 2005. 4. Larry Nyhoff, “Lập trình nâng cao bằng Pascal với các cấu trúc dữ liệu”, Dịch giả Lê Minh Trung, Công ty liên doanh tư vấn và dịch vụ khoa học kỹ thuật SCITEC, 1991. 5. Nguyễn Chí Trung, “Giáo trình Thuật toán và kĩ thuật lập trình Pascal”, Nhà xuất bản Hà Nội, 2005. Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 5 Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1. Thuật toán (giải thuật, thuật giải) 1.1. Định nghĩa Một thuật toán là một danh sách từng bước các chỉ dẫn để giải quyết cho một bài toán cụ thể. 1 Ở góc độ lập trình, thuật toán còn được gọi là thuật giải hay giải thuật, là một danh sách các thao tác (câu lệnh) theo đó máy tính thực hiện để sau một số hữu hạn bước, từ input là dữ liệu vào của bài toán, sẽ thu được output là dữ liệu ra cần tìm của bài toán. 1.2. Các tính chất cơ bản của thuật toán 1.2.1. Tính dừng Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác. Ví dụ: thuật toán sau đây vi phạm tính dừng Bước 1: S Å 0; i Å 0; Bước 2: i Å i + 1; Bước 3: S Å S + i*i; Bước 4: Quay về bước 2; Bước 5: Đưa ra S và kết thúc thuật toán Thuật toán được sửa lại để nó có tính dừng (trở thành thuật toán tính tổng các bình phương của n số tự nhiên đầu tiên) như sau: Bước 1: Nhập N; Bước 2: S Å 0; i Å 0; Bước 3: Nếu i ≥ N thì chuyển đến Bước 7; Bước 4: i Å i + 1; Bước 5: S Å S + i*i; Bước 6: Quay về bước 3; Bước 7: Đưa ra S và kết thúc thuật toán 1 Từ “thuật toán” (algorithm) xuất phát từ tên của quốc gia châu Á trung tâm cổ xưa là Khorezm, về sau là các nước cộng hòa xã hội chủ nghĩa Kazakh, Turkmen, and Uzbek. Vào khoảng năm 825 sau công nguyên, nghiên cứu chính về đại số và hệ thống khái niệm số học Ấn Độ được viết bởi Mohammed, là con trai của Musa (Khorez); tiếng Lattinh nghĩa là bởi “Mohamed ibn Musa al-Khowarizmi.” Vào năm 857, đoạn văn bản tiếng này được dịch sang tiếng Anh là "Algoritmi”. Từ đây, xuất phát từ cụm từ al-Khowarizmi, Hisab al-jabrw'sal-muqabalah (Mathematics-al-jabrw'sal muqabalah) mà chúng ta có tù algebra (đại số) Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 6 1.2.2. Tính xác định Thuật toán phải đảm bảo sau khi thực hiện một thao tác thì hoặc thuật toán kết thúc hoặc có đúng một thao tác hoàn toàn xác định để thực hiện tiếp theo. Ví dụ: thuật toán sau đây vi phạm tính xác định: Bước 1: Nhập a, b; Bước 2: Tính diện tích hình chữ nhật kích thước a, b hoặc tính thể tính hình nón đường cao a và bán kính hình tròn đáy là b. Tức là: S Å a * b hoặc S Å (1/3)π.a.b2Bước 3: Đưa ra S và kết thúc thuật toán Sửa lại Bước 1: Nhập a, b, nhập chọn lựa choice; //Qui ước choice = 1 là tính diện tích hình chữ nhật, ngược lại, tính thể tích hình nón Bước 2: Nếu choice = 1 thì S Å a * b và thực hiện bước 4; Bước 3: S Å (1/3)π.a.b2Bước 4: Đưa ra S và kết thúc thuật toán; Ví dụ khác: thuật toán ”Tìm số hạng Fibonacci thứ N” dưới đây vi phạm tính xác định Bước 1: Nhập số dương N Bước 2: Nếu N ≤ 2 thì c Å 1, kết thúc thuật toán Bước 3: a Å 1; b Å 1; k Å 2; Bước 4: Nếu k = N thì đưa ra c và kết thúc thuật toán, Bước 5: k Å k + 1; Thực hiện bước 6 hoặc bước 7 sau đây: Bước 6: c Å a + b; a Å b; b Å c; Quay về bước 4; Bước 7: c Å a + b; Bước 8: a Å b; b Å c; Quay về bước 4; Sửa lại: Bước 1: Nhập số dương N Bước 2: Nếu N ≤ 2 thì c Å 1, đưa ra c và kết thúc thuật toán Bước 3: a Å 1; b Å 1; k Å 2; Bước 4: Nếu k = N thì đưa ra c và kết thúc thuật toán, Bước 5: k Å k + 1; Bước 6: c Å a + b; a Å b; b Å c; Quay về bước 4; 1.2.3. Tính đúng đắn Một thuật toán phải đảm bảo cho ra Output luôn đúng đối với mọi dữ liệu vào của Input. Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 7 Ta định nghĩa một bộ dữ liệu vào đầy đủ là nó bao phủ hết (cover all the cases) tất cả các trường hợp cần xem xét. Ví dụ, để giải phương trình bậc 2: ax2 + bx + c = 0 (với a ≠0). Bộ Input đầy đủ là các giá trị tùy ý của a, b, c nhưng phải đủ trường hợp sau (với d = b2 - 4ac) d = 0, ví dụ (a, b, c) = (1, -2, 1) d > 0, ví dụ (a, b, c) = (1, 5, 4) d < 0, ví dụ (a, b, c) = (9, 2, 5) Như vậy, thuật toán đảm bảo tính đúng đắn nếu nó luôn cho kết quả (output) đúng đắn đối với một bộ dữ liệu vào đầy đủ. Ví dụ: Xét tính đúng đắn của thuật toán tính m = max (a, b,c) dưới đây: Bước 1: Nhập a, b, c; Bước 2: Nếu a < b thì m Å b Không thì Nếu a < c thì m Å c; Bước 3: Đưa ra m và kết thúc thuật toán; Rõ ràng thuật toán trên sai tại một số bộ dữ liệu, ví dụ nếu bộ dữ liệu vào là (a, b, c) = (1, 2, 3) thì thuật toán cho kết quả m = 2, không đúng yêu cầu của đề bài; nếu bộ dữ liệu vào là (a, b, c) = (2, 1, 3) thì không có chỉ thị nào trong thuật toán tác động vào m, do đó m không xác định và không tính được m như yêu cầu đề bài. Có thể sửa lại thuật toán như sau: Bước 1: Nhập a, b, c; Bước 2: m Å a; Bước 3: Nếu m < b thì m Å b; Bước 4: Nếu m < c thi m Å c; Bước 5: Đưa ra m và kết thúc thuật toán; 1.2.4. Tính phổ dụng Thuật toán phải đảm bảo giải được một lớp bài toán. Ví dụ thay vì xây dựng thuật toán và viết chương trình giải các phương trình: 1) 5x2 + 12x - 1 = 0 2) 2x2 -6x +2 = 0 3) 7x + 100 = 0 4) -50x2 +112x - 11 = 0 Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 8 Người ta tiến hành xây dựng thuật toán và viết chương trình giải phương trình: ax2 + bx + c = 0 với mọi số thực a, b, c cho trước. 1.3. Các tính quan trọng của thuật toán Các tính chất này liên quan đến việc nhấn mạnh ưu điểm của "thuật toán tin học" là có thể giao cho máy tính thực hiện. Một "thuật toán toán học" thuần túy có thể “rất đẹp” nhưng chưa chắc đã cài đặt dễ dàng trên máy tính, và nếu cài đặt được thì thuật toán đó chưa chắc ổn định và khả thi. Nói ở góc độ tương tự, hai tính chất sau đây thể hiện sự khác biệt giữa toán lí thuyết và toán tính. - Toán lí thuyết quan tâm đến các vấn đề định tính của bài toán: tồn tại, duy nhất, tính chất nghiệm của các bài toán. - Toán tính quan tâm đến xây dựng phương pháp, thuật toán để để tìm nghiệm bài toán trên máy tính. Thuật toán được xây dựng phải thỏa mãn yêu cầu về tính khả thi và tính ổn định. 1.3.1. Tính khả thi Một thuật toán là khả thi nếu nó thực hiện được trên máy tính trong một thời gian chấp nhận được. Thòi gian ở đây không tính đến kiểu CPU và chưa tính đến dung lượng bộ nhớ cần cấp phát. Ví dụ (tính khả thi). Cho hệ phương trình đại số tuyến tính bAx =, (1) trong đó A là ma trận vuông cấp n với định thức khác 0. Về lý thuyết, có thể giải hệ trên bằng thuật toán mà ý tưởng của nó dựa vào công thức Cramer: ∆∆=iix, (i =1, , n), (2) trong đó , còn là định thức của ma trận A sau khi thay cột i bởi cột tự do b. Nhưng việc tính toán ra nghiệm bằng số cụ thể lại là một việc không đơn giản. Theo công thức (2) cần phải tính n +1 định thức cấp n. Mỗi định thức là tổng của n! số hạng, mỗi số hạng là tích của n thừa số. Do vậy, để tính mỗi số hạng cần thực hiện n – 1 phép nhân. Như vậy, tất cả số phép tính nhân cần thực hiện trong (2) là Q = n!(n+1)(n-1). Adet=∆i∆Giả sử n = 20. Khi đó . Nếu tốc độ của máy tính là 100 triệu phép tính/giây thì thời gian để thực hiện khối lượng tính toán trên là giờ = năm. Một thời gian lớn vô cùng! Và như vậy, thuật toán dựa vào công thức Cramer là hoàn toàn không khả thi cho dù máy tính có tăng tốc độ lên gấp hàng nghìn, hàng vạn lần. 2010*7073.9≈Q910*2.6965510*0782.3Ở trên ta mới chỉ xét việc giải một hệ cỡ 20, mà thực tế khoa học và công nghệ đòi hỏi phải giải các hệ phương trình đại số tuyến tính cỡ hàng vạn, hàng triệu hoặc hơn thế nữa. Vì thế, cần phải Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 9 nghiên cứu đề xuất các phương pháp hiệu quả để có thể giải được các hệ thống phương trình cỡ lớn. 1.3.2. Tính ổn định Một thuật toán gọi là ổn định nếu sai số tính toán (do máy tính làm tròn số) không bị khuếch đại trong quá trình tính. Ví dụ (tính ổn định). Giả sử cần tính tích phân )1(110≥=−∫ndxexIxnn. Tích phân từng phần: đặt u = xn thì du = nxn-1dx; đặt dv = ex-1dx thì v = ex-1 ta được .111101101−−−−−=−=∫nxnxnnnIdxexnexI Ngoài ra ta có .3679.01)1(1011101≈=−==−−∫exedxexIxx Như vậy, để tính ta thu được công thức truy hồi tính được In về mặt lý thuyết: nI.3679.0,2,111=≥−=−InnIInn Về mặt thực tế tính trên máy tính không cho kết quả mong muốn khi n lớn. Cụ thể là tính trên máy tính với n = 25 ta được bảng kết quả sau (liệt kê theo từng hàng) 0.3679 0.2642 0.2073 0.1709 0.1455 0.1268 0.1124 0.1009 0.0916 0.0839 0.0774 0.0718 0.0669 0.0627 0.0590 0.0555 0.0572 -0.0295 1.5596 -30.1924 635.0403 -13969.8864 321308.3881 -7711400.3133 192785008.8325 Kết quả giảm dần từ 0.3679 (khi n = 1) đến 0.0555 (khi n=16). Kết quả sau đó kết quả thay đổi thất thường và giá trị tuyệt đối tăng rất nhanh. Điều này hoàn toàn không phù hợp với lý thuyết vì theo lý thuyết thì khi 0→nI∞→n do đó .11010+=≤≤∫ndxxInn Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 10 Hiện tượng kết quả tính toán nêu trên là sự không ổn định của thuật toán: sai số ban đầu khi tính nI3679.011≈=eI đã bị khuyếch đại trong quá trình tính. Cụ thể như sau: Thay vì tính chính xác eI11= ta tính xấp xỉ của nó là δ+=11~II , trong đó δlà sai số. Giả sử các tính toán tiếp theo không mắc phải sai số. Với n = 2 ta được .22)21()(21~21~21112δδδ−=−−=+−=−= IIIII Thu được 2~I với sai số δ2|~|22=− II . Tương tự, ở bước thứ n thay cho giá trị đúng ta thu được giá trị gần đúng với sai số . Do đó, dù nInI~δ!|~| nIInn=−δcó bé thì khi n đủ lớn, sai số vẫn đủ lớn và ta không thể nhận được giá trị chấp nhận được là gần đúng cho . nI2. Phân tích thuật toán 2.1. Tại sao phải phân tích thuật toán Xét một thuật toán nhân 2 số phức z1 = a + bi; z2 = c + di z = z1 * z2 = (ac – bd) + (ad + bc)i Khi tiến hành thuật toán: máy tính thực hiện 4 phép nhân và 3 phép cộng (ở đây là phép cộng đại số, nghĩa là phép trừ được xem là cộng với số âm). Giả sử phép nhân thực hiện mất 1 giây, phép cộng thực hiện mất 0.01 giây, phép gán thực hiện mất 0.005 giây. Khi đó phép nhân hai số phức trên thực hiện mất 4*1 + 3*0.01 + 0.005 = 4.035 giây. Để giảm thời gian tính toán, ta có thể giảm phép nhân nhờ các tính toán sau đây: ac - bd và ad + bc = (a + b)*(c + d) - ac - bd Do đó nếu đặt p := ac; q := bd; Thì z := (p - q) + ((a +b)*(c+d) - p - q)i Khi đó việc tính z gồm 3 phép nhân, 6 phép cộng và 3 phép gán; mất khoảng thời gian là 3*1 + 6*0.01 + 3*0.005 = 3.075 giây, giảm được 4.04 - 3.09 = 0.96 giây. Ví dụ trên cho thấy một bài toán có thể tồn tại nhiều thuật toán để giải, do đó cần lựa chọn thuật toán tốt nhất. Điều này cũng dẫn đến việc phân tích thuật toán. Ngoài ra, một bài toán được cài đặt bằng một thuật toán đúng, nhưng chưa chắc cho kết quả mong muốn. Vì các lí do sau: • Thời gian thực hiện quá lâu • Tốn nhiều bộ nhớ Điều này cũng dẫn đến cần phân tích thuật toán. Khi phân tích thuật toán, ta thường xem xét về thời gian và bộ nhớ chi phí cho thuật toán, trong đó chủ yếu phân tích về mặt thời gian. Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 11 2.2. Thời gian thực hiện thuật toán Thời gian thực hiện thuật toán phụ thuộc vào các yếu tố sau: 1. Kích thước dữ liệu đầu vào (ở đây ta sẽ kí hiệu là n). 2. Tốc độ máy tính 3. Ngôn ngữ lập trình 4. Kĩ thuật lập trình Các yếu tố (2), (3), (4) không đồng nhất đối với từng loại máy tính và ngôn ngữ lập trình. Vì thế thời gian thực hiện thuật toán được đánh giá chủ yếu dựa vào yếu tố (1) là kích thước dữ liệu đầu vào. Định nghĩa 1.1. Ta gọi T(n) là hàm thời gian phụ thuộc vào kích thước dữ liệu đầu vào n. Định nghĩa 1.2. Đơn vị tính của hàm T(n) không phải là đơn vị thời gian thực mà là số lần thực hiện các phép tính cơ bản. Các phép tính cơ bản là các phép toán có thời gian thực hiện bị chặn bởi một hàm số. Các phép tính cơ bản bao gồm: 1. Lời gọi thủ tục như read, write, và lời gọi hàm như sqr, sqrt, 2. Câu lệnh gán 3. Phép tính số học (+, -, *, /) 4. Phép toán logic và phép toán so sánh Chú ý: Ở đây ta không xem xét thời gian thực hiện đối với các câu lệnh điều khiển (rẽ nhánh if-then, case-of, lặp for-do, while-do, và repeat-until) vì chúng không được xem là các phép tính cơ bản. Việc bỏ qua các câu lệnh điều khiển mặc dù không cho kết quả chính xác về thời gian tính (khác nhau một cơ số lần giá trị của n, với n là kích thước dữ liệu vào), nhưng thường không ảnh hưởng đến độ phức tạp cần đánh giá. Vài trường hợp, câu lệnh rẽ nhánh khi kiểm tra điều kiện được quan tâm và thời gian của việc kiểm tra điều kiện này được tính là một hằng số nào đó. Một cách tổng quát, nếu mục đích là tính thời gian thực hiện thuật toán thì nên xem xét đầy đủ cả các câu lệnh điều khiển, nếu mục đích là đánh giá độ phức tạp thuật toán thì có thể bỏ qua các câu lệnh điều khiển. Ví dụ 1.1 Tính trung bình cộng của n số nhập từ bàn phím Số lần thực hiện 1. write(‘n = ‘); 1 2. readln(n); 1 3. T := 0; 1 for i := 1 to n do begin Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 12 4. write(‘x = ‘); n 5. readln(x); n 6. T := T + x; n end; 7. T := T/n; 1 Phân tích và đánh giá: Các lệnh 1, 2, 3 và 7 được thực hiện một lần. Thân vòng lặp gồm các lệnh 4, 5, 6 được thực hiện n lần. Vậy T(n) = 3n + 4. Định nghĩa 1.3. Có ba loại thời gian tính: • Thời gian tính tốt nhất: Là thời gian thực hiện nhanh nhất của thuật toán với một bộ dữ liệu vào nào đó. • Thời gian tính tồi nhất: Là thời gian thực hiện chậm nhất của thuật toán với một bộ dữ liệu vào nào đó. • Thời gian tính trung bình: Là trung bình cộng của các thời gian thực hiện thuật toán đối với tất cả các trường hợp thực hiện thuật toán (ứng với một bộ dữ liệu vào đầy đủ). Ví dụ 1.2 Tìm kiếm tuần tự Cho dãy số (a) gồm n phần tử a1, a2, , an. Hãy tìm vị trí của phần tử có giá trị bằng x cho trước trong dãy. 1. i := 1; 1 lần 2. found := false; 1 lần while (i <= n) and not found do if x = ai then 3. found := true; else 4. i := i + 1; if found then 5. writeln(‘vi tri ‘,i) else 6. writeln(‘khong tim thay’); 1 lần Phân tích và đánh giá: Mỗi câu lệnh 1, 2 luôn thực hiện 1 lần. Một trong hai lệnh 5 hoặc 6 thực hiện một lần. Vậy thời gian thực hiện thuật toán luôn có dạng T(n) = 3 + k, trong đó k là số lần thực hiện các câu lệnh 3 và 4. Khi đó ta có thể tạm thời không cần xem xét các câu lệnh 1, 2, 5, 6 nữa mà chỉ cần xem xét các câu lệnh 3 và 4. Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 13 Thời gian tính tốt nhất khi x = a1: Câu lệnh 3 thực hiện một lần, câu lệnh 4 thực hiện không lần, do đó k = 1 và : T(n) = 3 + 1 Thời gian tính tồi nhất xảy ra khi không có x trong dãy (không tìm thấy). Câu lệnh 3 thực hiện không lần, câu lệnh 4 thực hiện n lần. Do đó k = n và T(n) = 3 + n Thời gian tính trung bình được tính như sau: Nếu x = a1: T(n) = 3 + 1 (lệnh 3 một lần; lệnh 4 không lần) Nếu x = a2: T(n) = 3 + 2 (lệnh 3 một lần, lệnh 4 một lần) Nếu x = a3: T(n) = 3 + 3 (lệnh 3 một lần, lệnh 4 hai lần) …. Nếu x = an: T(n) = 3 + n (lệnh 3 một lần, lệnh 4 thực hiện n-1 lần) Nếu không thấy: T(n) = 3 + n (lệnh 3 không lần, lệnh 4 thực hiện n lần) Suy ra thời gian tính trung bình là : )1(269132)1(3)(2+++=+++++=nnnnnnnnnT Phân tích thuật toán theo nghĩa hẹp ở đây là xác định T(n) trong trường hợp xấu nhất. Phân tích thuật toán theo nghĩa rộng là việc lựa chọn thuật toán tốt: tốn ít bộ nhớ, và có thời gian tính trong trường hợp xấu nhất là chấp nhận được (tức là thỏa mãn tính khả thi). Một số vấn đề đặt ra: Khi phân tích thuật toán, người ta ít khi quan tâm đến tính chính xác của hàm thời gian tính mà thường quan tâm đến độ tăng của hàm này. Ví dụ 1.3 Đánh giá hàm thời gian khi n tăng Xét hàm thời gian T(n) = 60n2 + 9n + 19. Khi n tăng rất lớn thì T(n) ≈ 60n2 Giả sử T(n) được tính bằng giây, khi đó hàm T(n) trên đây tính bằng phút có dạng: T = n2 + 0,15n + 0,316. Khi n tăng rất lớn thì T(n) ≈ n2. Khi đó ta nói rằng T(n) có thời gian tính tương đương với hàm n2 , hay T(n) là VCL (vô cùng lớn) cùng bậc với n2, và ta viết T(n) = O(n2). Kí hiệu O đọc là kí hiệu big-O. Ở dưới đây ta có cách gọi khác, đó là T(n) có bậc không quá n2. Vậy trong quá trình phân tích thuật toán, ta cần tính T(n) theo kí hiệu Big-O. Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 14 2.3. Khái niệm độ phức tạp của thuật toán, kí hiệu big-O Định nghĩa 1.4. Cho f và g là hai hàm đối số nguyên dương. • Ta viết f(n) = O(g(n)) và nói f(n) có bậc không quá g(n) nếu tồn tại hằng số dương C1 và số nguyên N1 sao cho f(n) ≤ C1.g(n) với ∀n ≥ N1 Theo cách viết giới hạn, điều này nghĩa là: ∞→=nCngnf1)()(lim • Ta viết f(n) = Ω(g(n)) và nói f(n) có bậc ít nhất là g(n) nếu tồn tại hằng số dương C2 và số nguyên dương N2 sao cho f(n) ≥ C2.g(n) với ∀ n ≥ N2Theo cách viết giới hạn, điều này nghĩa là: ∞=∞→)()(limngnfn • Ta viết f(n) = θ(g(n)) và nói f(n) có bậc là g(n) nếu f(n) = O(g(n)) và f(n) = Ω(g(n)) Theo cách viết giới hạn, điều này nghĩa là: 0)()(lim =∞→ngnfn Theo định nghĩa trên, đánh giá thời gian tồi nhất của thuật toán chính là việc tính O(.), đánh giá thời gian tốt nhất của thuật toán là việc tính Ω(.). Định nghĩa 1.5. Khi hàm thời gian tính T(n) của thuật toán được biểu diễn qua kí hiệu big-O thì T(n) được gọi là độ phức tạp thuật toán (Complexity of Algorithms). Ví dụ 1.4 Biểu diễn hàm thời gian theo các kí pháp big-O, omega, theta Xét hàm T(n) = 60n2 + 9n + 1, 1) Tính O(.) Ta có 60n2 + 9n + 1 ≤ 60n2 + 9n2 + n2 = 70n2 với ∀ n ≥ 1 Chọn C1 = 70, g(n) = n2, N1 = 1 Æ T(n) ≤ C1.g(n) hay T(n) = O(n2) 2) Tính Ω(.) Ta có 60n2 ≤ 60n2 + 9n + 1 với ∀ n ≥ 1 Chọn C2 = 60 , N2 = 1 Æ T(n) = Ω(n2) 3) Tính θ(.) Vì O(n2) = T(n) = Ω(n2) Æ T(n) = θ(n2). Các hàm đánh giá thông dụng: Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 15 STT Hàm Tên gọi: độ phức tạp Đánh giá 1 O(C), O(1) Hằng số 2 O(log2n) logarit 3 O(n) tuyến tính 4 O(nlogn) nlog2n 5 O(n2) bậc 2 6 O(n3) bậc 3 7 O(nk) đa thức Chấp nhận được 8 O(an) hàm mũ 9 O(n!) giai thừa Không chấp nhận được Ví dụ 1.5 Dùng kí hiệu θ đánh giá tốc độ tăng của hàm a) 222)1()(2nnnnnf +=+= Chọn C1 = 1; N1 = 1; C2 = 1/2; N2 = 1, g(n) = n2, ta có: f(n) ≤ n2/2 +n2/2 = n2 với ∀ n ≥ N1 Æ f(n) ≤ C1.g(n) Æ f(n) = O(n2) f(n) = n2/2 + n/2 ≥ n2/2 với ∀ n ≥ N2 Æ f(n) ≥ C2.g(n) Æ f(n) = Ω(n2) Do đó f(n) = θ(n2). b) 12111)(2++−=++=nnnnnf Ta có 1121 ≥∀≤++− nnnn, đó đặt C1=1; N1=1 thì f(n) = O(n) Và vì 112121≥∀++−≤ nnnn nên đặt C2 = 1/2; N2=2 thì f(n) = Ω(n) Suy ra f(n) = θ(n). 3. Các qui tắc xác định độ phức tạp thuật toán 3.1. Qui tắc hằng số Nếu một thuật toán T có thời gian thực hiện T(n) = O(C.f(n)) với C là hằng số dương thì có thể coi thuật toán T có độ phức tạp tính toán là O(f(n)). Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 16 Chứng minh: Vì T(n) = O(C.f(n)) nên tồn tại số dương C1 và số nguyên N1 sao cho T(n) ≤ C.C1.f(n) với ∀ n ≥ N1. Khi đó chọn C2 = C.C1 thì T(n) ≤ C2.f(n) với ∀ n ≥ N1, hay T(n) = O(f(n)). 3.2. Qui tắc cộng Giả sử một thuật toán T gồm hai phần liên tiếp T1 và T2. Và, giả sử phần T1 có thời gian thực hiện là T1(n) = O(f(n)); phần T2 có thời gian thực hiện là T2(n) = O(g(n)). Khi đó thời gian thực hiện thuật toán sẽ là T(n) = T1(n) + T2(n) = O(f(n) + g(n)) Chứng minh: Vì T1 = O(f(n)) nên tồn tại hằng số dương C1 và số nguyên N1 sao cho T1(n) ≤ C1.f(n) với ∀ n ≥ N1. Và vì T2 = O(g(n)) nên tồn tại hằng số dương C2 và số nguyên N2 sao cho T2(n) ≤ C2.g(n) với ∀ n ≥ N2. Chọn C0 = max(C1, C2) và N0 = max(N1, N2) thì với ∀ n ≥ N0 ta có: T(n) = T1(n) + T2(n) ≤ C1.f(n) + C2.g(n) ≤ C0.f(n) + C0.g(n) = C0(f(n)+g(n)). Do đó T(n) = O(f(n) + g(n)). 3.3. Qui tắc lấy max Nếu thuật toán T có thời gian thực hiện T(n) = O(f(n) + g(n)) thì có thể coi thời gian thực hiện thuật toán T có độ phức tạp là T(n) = O(max(f(n), g(n)). Chứng minh: Vì T(n) = O(f(n) + g(n)) nên tồn tại số dương C1 và số nguyên N1 sao cho với ∀ n ≥ N1 thì T(n) ≤ C1.(f(n) + g(n)) = C1.f(n) + C1.g(n) ≤ 2C1.max(f(n), g(n)). Do đó T(n) = O(max(f(n), g(n))). Chú ý: Qui tắc max rất hay được sử dụng. Với qui tắc này: • Nếu T(n) là một đa thức thì có thể khẳng định các toán hạng bậc thấp là không quan trọng, có thể bỏ qua khi đánh giá độ phức tạp thuật toán. • Trong một đoạn chương trình, câu lệnh được thực hiện nhiều nhất (được gọi là câu lệnh đặc trưng) sẽ được sử dụng để đánh giá độ phức tạp thuật toán của đoạn chương trình đó, mà không cần quan tâm đến các câu lệnh khác (điều này không đúng nếu tính thời gian thực hiện thuật toán cho toàn bộ đoạn chương trình). Câu lệnh đặc trưng thường là câu lệnh đơn nằm trong một vòng lặp ở mức sâu nhất. Việc đánh giá độ phức tạp thuật toán sử dụng câu lệnh đặc trưng sẽ được dùng đến từ phần áp dụng của chương 3, hiện tại không dùng đến để rèn luyện việc phân tích thuật toán. Ví dụ 1.6. Minh họa qui tắc max a) T(n) = 3n + 4 (Trong Ví dụ 1.1). Ta có T(n) = 3n + 4n0 Æ T(n) = O(n). Vậy thuật toán tính giá trị trung bình có độ phức tạp tuyến tính. b) )1(269)(2+++=nnnnT(Trong Ví dụ 1.2). Ta có Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 17 696969)1(269)(0022=≥∀+≤++=++≤+++= NnnnnnnnnnnnnT )()( nOnT =→ Vậy thuật toán tìm kiếm tuần tự có độ phức tạp tuyến tính. c) T(n) = 60n2 + 9n + 9 (Trong Ví dụ 1.3). Ta có T(n) = O(n2) Vì chọn N0 = 9 và C0 = 70 thì với ∀ n ≥ N0 ta có 60n2 + 9n + 9 ≤ 60n2 + 9n2 + n2 = 70n2. Do đó T(n) ≤ C0.n2 với ∀n ≥ N0 hay T(n) = O(n2). 3.4. Qui tắc nhân Nếu đoạn thuật toán T có thời gian thực hiện T(n) = O(f(n)). Khi đó nếu thực hiện k(n) lần đoạn thuật toán T với k(n) = O(g(n)) thì độ phức tạp tính toán của quá trình lặp này là: T(n) = O(f(n).g(n)). Chứng minh: Thời gian thực hiện k(n) đoạn thuật toán T sẽ là k(n).T(n). Theo định nghĩa big-O ta có: - Tồn tại hằng số dương Ck và số nguyên Nk sao cho k(n) ≤ Ck.g(n) với ∀ n ≥ Nk- Tồn tại hằng số dương Cr và số nguyên Nr sao cho T(n) ≤ Cr.f(n) với ∀ n ≥ Nr. Vậy nếu đặt N0 = max(Nk, Nr) và C0 = Ck.Cr thì với ∀ n ≥ N0 ta có: k(n).T(n) ≤ C0.f(n).g(n) hay độ phức tạp tính toán của quá trình lặp là T(n) = O(f(n).g(n)). 4. Các kỹ thuật đánh giá độ phức tạp thuật toán 4.1. Câu lệnh đơn Câu lệnh đơn là câu lệnh thực hiện một thao tác, ví dụ câu lệnh gán đơn giản (không chứa lời gọi hàm trong biểu thức), câu lệnh vào/ra đơn giản, câu lệnh chuyển điều khiển đơn giản như break, goto, continue, return. Thời gian thực hiện một câu lệnh đơn không phụ thuộc vào kích thước dữ liệu nên sẽ là O(1). Nói cách khác, các câu lệnh đơn có thời gian tính bị chặn bởi hàm số O(1) (hay O(c)). Ví dụ mỗi câu lệnh sau đều có thời gian thực hiện là O(1): readln; writeln; readln(x); writeln(k); 4.2. Câu lệnh hợp thành Thời gian thực hiện một câu lệnh hợp thành sẽ được tính theo qui tắc cộng và qui tắc max. Ví dụ 1.7 Minh họa qui tắc cộng if n > 1 then begin 1. s := sqrt(n) 1 lần 2. readln(x); 1 lần Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 18 if s > x then 3. s := s - x; else 4 s := x - s; 1 lần end; Hiển nhiên T(n) = 1 + 1 + 1 = 3 (đúng như qui tắc cộng) Æ T(n) = O(1) Ví dụ 1.8 Minh họa qui tắc max đối với câu lệnh hợp thành if n > 1 then begin for i :=1 to n do 1. write(i*i:6); n lần 2. writeln; 1 lần end; Dễ thấy T(n) = 1 + n Æ T(n) = O(n) Đúng như qui tắc max: T(n) = O(max(1, n)) = O(n) 3.3. Câu lệnh lặp với số lần lặp biết trước for-do for i := 1 to n do P(i); Trong đó P(i) là một câu lệnh hoặc một khối lệnh (câu lệnh hợp thành) trong thân vòng lặp. Có hai trường hợp: Trường hợp 1: Thời gian thực hiện P(i) là một hằng số và không phụ thuộc vào i, nghĩa là T(P(i)) = t , với t là hằng số. Khi đó thời gian thực hiện câu lệnh lặp là n lần thực hiện P(i), tức là: tnnT .)( = Ví dụ 1.9. Đánh giá thời gian tính của vòng lặp khi P(i) là hằng số for i := 1 to n do begin 1. write(‘x = ‘); 2. readln(x); 3. S := S + x; end; ⎪⎪⎭⎪⎪⎬⎫P(i) T(P(i)) = 3. Do đó T(n) = n.3 Æ T(n) = O(n) Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 19 Trường hợp 2: Thời gian thực hiện của P(i) phụ thuộc vào i, nghĩa là T(P(i)) = t(i). Khi đó thời gian thực hiện câu lệnh lặp “for i” với i lần lượt nhận giá trị từ 1 đến n là T(n) = t(1) + t(2) + … + t(n), hay ta có: ∑==niitnT1)()( Ví dụ 1.10. Đánh giá thời gian tính của vòng lặp khi P(i) phụ thuộc i for i := 1 to n do begin for j:=1 to i do 1. write(j:5); 2. writeln; end; ⎪⎪⎭⎪⎪⎬⎫P(i) )()(21212)1()1()(1))((2121nOnTnnnnnininTiiPTnini=→+=++=+=+=→+=∑∑== 3.4. Câu lệnh rẽ nhánh if Giả sử thời gian thực hiện hai câu lệnh thành phần của câu lệnh if dạng đủ là f(n) và g(n). Khi đó thời gian thực hiện câu lệnh if sẽ được tính theo qui tắc max, tức là sẽ bằng O(max(f(n), g(n)). Thời gian kiểm tra điều kiện thường là hằng số, tức là O(1). Ví dụ 1.11. Minh họa thời gian tính của câu lệnh rẽ nhánh if n < 1 then 1. writeln(‘hay nhap so nguyen duong’) 1 lần else for i :=1 to n do 2. write(i : 5); ⎭⎬⎫n lần T(n) = max (1, n) = n Æ T(n) = O(n) 3.5. Câu lệnh lặp với số lần lặp chưa biết trước while, repeat Để đánh giá thời gian thực hiện câu lệnh lặp này ta dựa vào kinh nghiệm: Ví dụ 1.12 Thời gian tính đối với vòng lặp while đơn giản 1. i := n; 1 lần Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 20 2. S := 0; 1 lần while i > 0 do begin 3. write(‘x = ‘); 4. readln(x); 5. S := S + x; 6. i : = i - 1; end; P(i) lần T((P(i)) = 4 Æ T(n) = 2 + 4.T(P(i)) = 2 + 4n Æ T(n) = O(n) Ví dụ 1.13 Độ phức tạp của vòng while mà biến điều khiển thay đổi không liên tục 1. i := n; 1 lần 2. S := 0; 1 lần while i > 0 do begin 3. write(‘x = ‘); 4. readln(x); 5. S := S + x; 6. i : = i div 2; P(i) gồm 4 câu lệnh cơ bản end; Phân tích, đánh giá: P(i) gồm 4 câu lệnh cơ bản 3, 4, 5, và 6 - i = n/20 Æ P(i) thực hiện lần thứ nhất - i = n/21 Æ P(i) thựchiện lần thứ hai - i = n/22 Æ P(i) thựchiện lần thứ ba - … - i = n/2k-1 Æ P(i) thực hiện lần thứ k Nếu đây là lần thực hiện cuối cùng thì n/2k-1 = 1 Ù n = 2k-1 Ù k = log2n + 1 Khi đó T(n) = 2 + 4k = 2 +4(log2n + 1) = 4log2n + 6 Æ với ∀ n ≥ 2 thì T(n) ≤ 4log2n + 6log2n = 10log2n Chọn f(n) = log2n, N0 = 2; C0 = 10 ta có T(n) ≤ C0f(n) với ∀ n ≥ N0. Do đó: T(n) = O(log2n). Ví dụ 1.14 Độ phức tạp của vòng lặp while phức tạp hơn 1. i := n; 1 lần Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 21 2. S := 0; l lần while i > 0 do begin 3. for j := 1 to i do 4. write(j:5); 5. writeln; 6. i := i div 2; )(iP⎪⎭⎪⎬⎫ end; Phân tích, đánh giá: P(i) gồm hai câu lệnh cơ bản 5 và 6, và một câu lệnh cơ bản 4 thực hiện i lần. - Lần 1: i = n/20 Æ thực hiện n + 2 câu lệnh cơ bản - Lần 2: i = n/21 Æ thực hiện n/2 + 2 câu lệnh cơ bản - Lần 3 i = n/22 Æ thực hiện n/22 + 2 câu lệnh cơ bản - … - Lần k: i = n/2k-1 Æ thực hiện n/2k + 2 câu lệnh cơ bản Nếu đây là lần thực hiện cuối cùng thì n/2k-1 = 1 Ù n = n/2k-1 Ù k = log2n + 1. Khi đó: 1221222log242112112log22)21 21211(22)(−−−++=−−+++=++++++=kkknnnnnnknT Do đó T(n) ≤ 2n + 2log2n + 4 ≤ 2n + 2n + 4n = 8n (vì khi n tăng thì log2n ≤ log22n =n). Vậy T(n) = O(n). 5. Một số ví dụ minh họa thiết kế thuật toán và đánh giá độ phức tạp Bài toán 1.1. Tính giá trị gần đúng của exp(x) theo khai triển Taylor ! !2!112nxxxenx++++= a) Thiết kế giải thuật b) Đánh giá độ phức tạp Giải Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 22 a) 1, 2 s := 1; p := 1; for i :=1 to n do begin 3. p := p * x/i; 4. s := s + p; ⎭⎬⎫P(i) end; b) T(n) = 2 + 2*n Æ T(n) = O(n) Bài toán 1.2 Thuật toán tìm kiếm tuần tự Cho dãy gồm n phần tử a1, a2, , an. Hãy đưa ra vị trí của phần tử đầu tiên bằng phần tử đứng ngay trước đó trong dãy. a) Thiết kế giải thuật b) Đánh giá độ phức tạp Giải Ví dụ 6, 7, 3, 4, 9, 8, 1, 5, 2, 5, 4, 3 Đáp số là vị trí 7 a) 1, 2 i := 2; found := false; 1 lần while (i<=n) and not found do 3. if a[i] = a[i-1] then found := true 4. else i := i + 1; ⎭⎬⎫P(i) 5. if found then write(‘Vi tri can tim: ‘, i) 6. else write(‘khong co phan tu nao nhu vay’); 1 lần Trong trường hợp xấu nhất, lệnh rẽ nhánh đủ - thân vòng lặp while thực hiện n-1 lần. Do đó ta có T(n) = 2 + (n-1) + 1 = n + 2 Æ T(n) = O(n). Bài toán 1.3 Thuật toán tìm kiếm nhị phân Cho dãy n số a1, a2, , an đã được sắp xếp tăng. Hãy đưa ra vị trí của phần tử trong dãy có giá trị bằng x cho trước. Giải 1. d := 1; 1 lần 2. c := n; 1 lần 3. found := false; 1 lần Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 23 while (d <= c) and not found do begin 4. k := (d+c) div 2; 5. if x < a[k] then c := k - 1 6. else if x > a[k] then d := k + 1 7. else found := true; ⎪⎪⎭⎪⎪⎬⎫P(i) end; 8. if found then write(‘Tim thay o vi tri ‘, k) 9. else write(‘khong co x trong day’); 1 lần Trong trường hợp xấu nhất, không có x trong dãy, ta cần tính số lần thực hiện khối lệnh P(i) trong thân vòng lặp, gồm 2 lệnh cơ bản. Vì mỗi lần đi qua vòng lặp độ dài của dãy giảm đi một nửa, nên sau vòng lặp thứ k độ dài của dãy còn là n/2k. Vòng lặp kết thúc tại lần thứ k mà độ dài còn lại của dãy là n/2k = 1 hay k = log2n. Khi đó: T(n) = 4 + 2k = 4 + 2log2n ≤ log2n + 2log2n với ∀ n ≥ N0 = 3. T(n) ≤ 3log2n Æ T(n) = O(log2n). Bài toán 1.4 Thuật toán sắp xếp chọn lựa Cho dãy (a) gồm n số a1, a2, , an. Hãy sắp xếp dãy (a) theo thứ tự không giảm. Thuật toán sắp xếp chọn trực tiếp kinh điển (chưa tối ưu) for i :=1 to n-1 do begin (* chọn phần tử nhỏ nhất trong dãy a[i] đến a[n]*) 1. k := i ; (*vị trí của phần tử nhỏ nhất*) n-1 lần 2. min := a[i] (*giá trị phần tử nhỏ nhất*) n-1 lần for j := i + 1 to n do if a[j] < min then begin 3. k := j; 4. min := a[j]; end; ⎪⎪⎭⎪⎪⎬⎫P(i) if (k<>i) then begin 5. a[k] := a[i]; n-1 lần 6. a[i] := min; end; end; n-1 lần Xét thuật toán trong trường hợp tồi nhất: dãy (a) đã được sắp xếp không tăng. Ta cần đánh giá được số lần thực hiện hai câu lệnh cơ bản 3 và 4, do đó tính được thời gian P(i) để thực hiện các câu lệnh for j phụ thuộc vào i. Phân tích thiết kế thuật toán và đánh giá độ phức tạp giải thuật 24 - i = 1: hai câu lệnh 3 và 4 thực hiện n - 1 lần - i = 2: hai câu lệnh 3 và 4 thực hiện n - 2 lần - … - i = n-1: hai câu lệnh 3 và 4 thực hiện n- (n-1) = 1 lần Vậy T(P(i)) = 1 + 2 + … + (n-2) + (n-1) = n(n-1)/2 (ta đặt bằng p) Do đó T(n) = 4(n-1) + n(n-1)/2 = (1/2)n2 + (7/2)n - 4. Vậy T(n) = O(n2). Thuật toán sắp xếp chọn trực tiếp cải tiến (tối ưu hơn) for i :=1 to n-1 do begin (* chọn phần tử nhỏ nhất trong dãy a[i] đến a[n]*) 1. k := i ; (*vị trí của phần tử nhỏ nhất*) n-1 lần for j := i + 1 to n do 2. if a[j] < a[k] then k := j; p lần 3. if k<> i then begin 4. tg := a[i]; 5. a[i] := a[k]; 6. a[k] := tg; end; n-1 lần end; Do đó T2(n) = 2(n-1) + n(n-1)/2 = (1/2)n2 + (3/2)n - 2. Vậy T2(n) = O(n2). Ta thấy khi thay đổi thuật toán, độ phức tạp không thay đổi nhưng thời gian tính toán ít hơn. 6. Phân tích chương trình (con) đệ qui 6.1. Khái niệm về đệ qui Khái niệm về đề qui dẫn đến một loạt các khái niệm như bài toán đệ qui, lời giải đệ qui, thuật toán đệ qui và cuối cùng là chương trình con đệ qui. Ta nói: một đối tượng là đệ qui khi 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ó. Bài toán T gọi là bài toán đệ qui nếu nó được giải bằng một bài toán T’ có dạng giống như T, nói cách khác T là bài toán được giải bằng một thuật toán đệ qui. Nguyễn Chí Trung – Nguyễn Thị Thu Thủy 25 Ví dụ về hình ảnh đệ qui: giả sử cần xác định một cái túi: Cần lấy một cái túi mà nó đựng trong một cái túi thứ hai mà cái túi thứ hai này là một cái túi mà nó đựng trong một cái túi thứ ba, cái túi thứ ba là một cái túi mà nó đựng trong cái túi thứ tư, Tuy nhiên quá trình các cái túi chứa trong nhau ấy không thể vô hạn, đến một cái túi thứ n hữu hạn nào đó thì nó không đựng trong một cái túi nào nữa. Cái túi thứ n này gọi là cái túi “neo”, các cái túi còn lại gọi là các cái túi được xác định một cách đệ qui. Trong toán học, ta gặp rất nhiều định nghĩa đệ qui mà thường là các công thức để tính giá trị cho một hàm số nào đó có thể tính được bằng qui nạp toán học (hay công thức truy hồi). Ví dụ 1.15 Định nghĩa đệ qui hàm tính n! Ta có thể định nghĩa f(n) = n! như sau: ⎩⎨⎧>−==0)1(.01)(nifnfnnifnf Như vậy bài toán T tính f(n) được giải dựa vào bài toán T’ tính f(n-1) có dạng giống như T. Bài toán T’ tính f(n-1) lại được giải dựa vào bài toán T” tính f(n-2) có dạng giống như T’ (hoặc như T), cứ tiếp tục quá trình đệ qui đó và cuối cùng đến phần “neo”, ta nhận được bài toán Tn’ được giải hoàn toàn khác, đó là f(0) = 1. 6.2. Chương trình (con) đệ qui Chương trình con thể hiện một thuật toán đệ qui gọi là chương trình (con) đệ qui. Định nghĩa một chương trình con đệ qui phản ánh chính xác định nghĩa công thức đệ qui, nghĩa là gồm hai phần • Phần neo: Lời gọi hàm hay thủ tục được thực hiện bằng một lời giải đã biết. • Phần đệ qui: Lời gọi chính hàm hay thủ tục đó nhưng có kích thước dữ liệu đầu vào thay đổi theo xu hướng (thường là nhỏ hơn) để quá trình đệ qui dẫn đến phần neo. Ví dụ 1.16 Chương trình (con) đệ qui tính hàm giaithua(n) = n! function giaithua(n:integer): longint; begin if n = 0 then giaithua := 1 else giaithua := n*giaithua(n-1); end; 6.3. Xây dựng phương trình (công thức) đệ qui Phương trình đệ qui là phương trình thể hiện mối quan hệ giữa T(n) và T(k). Trong đó T(n) là thời gian thực hiện thuật toán với dữ liệu vào kích thước là n, T(k) là thời gian thực hiện chính thuật toán đó nhưng với dữ liệu kích thước là k. Ví dụ 1.17 Xây dựng phương trình đệ qui tính hàm giaithua(n)

Trích đoạn

• Sơ đồ chung của thuật toán chia để trị
• Phương pháp chung của qui hoạch động
• Trở lại bài toán mảng con trọng số lớn nhất
• Bài toán cái túi
• Thuật toán Prim

Tài liệu liên quan

• 2.Đánh giá độ phức tạp của giải thuật sắp xếp bằng phương pháp chèn(Insertion Sort)
  • 11
  • 5
  • 5
• Giáo trình phân tích thiết kế hệ thống thông tin
  • 115
  • 767
  • 1
• Tài liệu Giáo trình Phân tích thiết kế hệ thống thông tin quản lý ppt
  • 38
  • 575
  • 1
• Giáo trình: Phân tích thiết kế hệ thống pptx
  • 191
  • 495
  • 1
• giáo trình phân tích, thiết kế xây dựng và quản trị các hệ thống cơ sở dữ liệu
  • 400
  • 715
  • 3
• Giáo trình phân tích thiết kế hệ thống -Chương 1 pdf
  • 17
  • 559
  • 0
• Giáo trình phân tích thiết kế hệ thống -Chương 5 pot
  • 14
  • 410
  • 0
• Giáo trình phân tích thiết kế hệ thống thông tin
  • 74
  • 383
  • 1
• giáo trình phân tích thiết kế hệ thống thông tin
  • 125
  • 222
  • 1
• giáo trình phân tích thiết kế hệ thống thông tin
  • 124
  • 385
  • 2

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(1.82 MB - 96 trang) - [Giáo trình] Phân tích thiết kế thuật toán và đánh giá độ phức tạp của giải thuật - ĐH Sư phạm Hà Nội Tải bản đầy đủ ngay ×