Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 4: Phân tích thuật toán

Nội dung text: Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 4: Phân tích thuật toán

1. Phân tích thuật toán Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. Phân tích độ phức tạp • Mục tiêu: Đánh giá hiệu năng (thời gian chạy và bộ nhớ chiếm dụng) của các thuật toán • Cho phép: − So sánh các thuật toán khác nhau cùng giải một bài toán − Xem thời gian chạy biến thiên như thế nào theo kích thước dữ liệu đầu vào • Phân tích độ phức tạp (complexity) bằng cách đếm số thao tác (operation) chiếm nhiều thời gian nhất • Phân tích tiệm cận (asymptotic analysis): − Xem thời gian chạy tăng nhanh như thế nào khi kích thước đầu vào dần đến vô cùng
3. Ví dụ đếm số thao tác Ví dụ 1: Ví dụ 3: for (i=0; i cout a[i+1]) ma trận tam giác dưới và véc-tơ sorted = false; ci  0, i = 1 to n return sorted; for i = 1 to n } for j = 1 to i ci += aij bj; Số phép so sánh = n - 1 n Số phép nhân = i=1 i = n(n+1)/2
4. Phân tích độ phức tạp tiệm cận • Xem xét sự tăng trưởng của hàm t = f(n) khi n − n là kích thước dữ liệu đầu vào (VD: số phần tử của mảng) − t là thời gian chạy (hay độ phức tạp) • Phân tích tiệm cận của f(n) sẽ − độc lập với các hệ số (VD: bỏ qua 10 trong 10n2) − độc lập với các số hạng bậc thấp (VD: bỏ qua n trong n2 + n) • Các độ đo tiệm cận: − Ô lớn: O − Ô-mê-ga lớn:  − Tê-ta lớn: 
5. Ký hiệu Ô lớn • f(n) = O(g(n)) − khi và chỉ khi  c > 0 và n0 > 0 sao cho f(n) cg(n) n n0 cg(n) f(n) f(n) bị chặn trên bởi g(n) theo nghĩa tiệm cận n0
6. Ký hiệu Ô-mê-ga lớn • f(n) = (g(n)) − khi và chỉ khi  c > 0 và n0 > 0 sao cho cg(n) f(n) n n0 f(n) cg(n) f(n) bị chặn dưới bởi g(n) theo nghĩa tiệm cận n0
7. Ký hiệu Tê-ta lớn • f(n) = (g(n)) − khi và chỉ khi  c1 > 0, c2 > 0 và n0 > 0 sao cho c1g(n) f(n) c2g(n) n n0 c2g(n) f(n) c1g(n) f(n) có cùng tốc độ tăng với g(n) n0
8. Ví dụ f(n) = 3n2 + 17 − (1), (n), (n2) các cận dưới − O(n2), O(n3), các cận trên − (n2) cận chính xác Hãy điền vào dấu chấm hỏi sau đây ! f(n) = 1000 n2 + 17 + 0.001 n3 − (?) các cận dưới − O(?) các cận trên − (?) cận chính xác
9. Tính chất bắc cầu • Nếu f(n) = O(g(n)) và g(n) = O(h(n)) f(n) = O(h(n)) • Nếu f(n) = (g(n)) và g(n) = (h(n)) f(n) = (h(n)) • Nếu f(n) = (g(n)) và g(n) = (h(n)) f(n) = (h(n))
10. Một số quy tắc k • Nếu f(n) = a0 + a1n + + akn (đa thức bậc k) f(n) = O(nk) • logkn = O(n) với k là một hằng số − Hàm lôgarit tăng rất chậm so với hàm tuyến tính
11. Tốc độ tăng của một số hàm cơ bản Hàm Tên c Hằng log n Lôgarit log2 n Log bình phương n Tuyến tính n log n n2 Bậc hai n3 Bậc ba 2n Hàm mũ
12. Ví dụ • f(n) = n log n and g(n) = n1,5 − Hàm nào tăng nhanh hơn? • Chú ý rằng g(n) = n1,5 = n*n0,5 − Vì vậy, chỉ cần so sánh tốc độ tăng của log n và n0,5 − Tương đương với so sánh log2n và n − Tham khảo bảng trong slide trước log2n tăng chậm hơn n f(n) tăng chậm hơn g(n)
13. Tính thời gian chạy: Vòng lặp for (j = 0; j < n; ++j) { // 3 thao tác cơ bản } • Một thao tác cơ bản (VD: phép so sánh, phép nhân, ) được thực hiện trong thời gian hằng số • Số thao tác cơ bản: − n bước lặp và mỗi bước lặp có 3 thao tác cơ bản 3n (Ở đây ta có thể bỏ qua chi phí của bản thân việc lặp: • Một phép gán khởi tạo: j = 0 • n phép tăng của j • n + 1 phép so sánh giữa j và n) • Độ phức tạp = 3n = O(n)
14. Vòng lặp với câu lệnh break for (j = 0; j < n; ++j) { // 3 thao tác cơ bản if (điều-kiện) break; } • Độ phức tạp = 4n = O(n) (số 4 vì có 3 thao tác cơ bản và 1 điều kiện)
15. Tìm kiếm tuần tự • Cho mảng a có n phần tử, tìm vị trí của phần tử x for (i = 0; i < n; i++) { if (a[i] == x) return i; } return -1; • Trong trường hợp tồi nhất (x nằm ở cuối mảng hoặc x không có trong mảng), phải thực hiện n phép so sánh a[i] với x Độ phức tạp = O(n)
16. Câu lệnh if-else if (điều-kiện) // 1 i = 0; // 1 else for (j = 0; j < n; j++) a[j] = j; n Độ phức tạp = 1 + max (1, n) = 1 + n = O(n)
17. Các câu lệnh lặp tuần tự • Cộng độ phức tạp của các câu lệnh tuần tự for (j = 0; j < n; ++j) { // 3 thao tác cơ bản } for (j = 0; j < n; ++j) { // 5 thao tác cơ bản } Độ phức tạp = 3n + 5n = 8n = O(n)
18. Các câu lệnh lặp lồng nhau • Phân tích các câu lệnh lặp từ trong ra ngoài for (j = 0; j < n; j++) { // 2 thao tác cơ bản for (k = 0; k < n; k++) { // 3 thao tác cơ bản } } Độ phức tạp = (2 + 3n)n = 3n2 + 2n = O(n2)
19. Đệ quy long factorial(int n) { if (n 1 thì có 1 phép so sánh, 1 phép nhân, 1 phép trừ (tổng của 3 phép này là hằng, tức là 1) và 1 lời gọi đệ quy: t(1) = 1 t(n) = 3 + t(n - 1) = 3 + 3 + t(n - 2) = 3 + 3 + 3 + t(n - 3) = = 3k + t(n - k) • Chọn k = n - 1: t(n) = 3(n – 1) + t(1) = 3(n – 1) + 1 = 3n - 2 = O(n)
20. Phân tích đệ quy • Viết biểu thức đệ quy • Liên tục thay thế và phát hiện quy luật • Chọn giá trị của k để đi đến trường hợp cơ sở – Có thể phải định giá một chuỗi để đi đến lời giải
21. Ví dụ về phân tích đệ quy long f(int n) Viết biểu thức đệ quy: { t(1) = 1 if( n <= 1 ) t(n) = 3 + t(n - 1) return 1; else Liên tục thay thế và phát hiện quy luật: return 1 + f(n-1); t(n) = 3 + t(n - 1) } = 3 + 3 + t(n - 2) = 3+ 3 + 3 + t(n - 3) = 3k + t(n - k) Chọn k để dẫn đến trường hợp cơ sở: Cho n - k = 1 hay k = n - 1, khi đó ta có t(n) = 3(n - 1) + t(1) = 3n - 2 = O(n)