Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 4: Phân tích thuật toán - Nguyễn Mạnh Hiển

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 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 Ví dụ đếm số thao tác Ví dụ 1: for (i=0; i<n; i++) cout << a[i] << endl; Ví dụ 3: template bool isSorted(T *a, int n) { bool sorted = true; for (int i=0; i<n-1; i++) if (a[i] > a[i+1]) sorted = false; return sorted; } Số lần xuất = n Số phép so sánh = n - 1 Ví dụ 2: Mã giả của phép nhân ma trận tam giác dưới và véc-tơ ci  0, i = 1 to n for i = 1 to n for j = 1 to i ci += aij bj; Số phép nhân = i=1 n i = n(n+1)/2 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:  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 f(n) cg(n) n0 f(n) bị chặn trên bởi g(n) theo nghĩa tiệm cận 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) n0 f(n) bị chặn dưới bởi g(n) theo nghĩa tiệm cận 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 f(n) c1g(n) n0 c2g(n) f(n) có cùng tốc độ tăng với g(n) 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 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)) Một số quy tắc • Nếu f(n) = a0 + a1n + + akn k (đ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 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ũ 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) 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) 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) 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) 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; Độ phức tạp = 1 + max (1, n) = 1 + n = O(n) n 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) 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) Đệ quy long factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1); } • Khi n = 1 thì chỉ có 1 phép so sánh, còn khi 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) 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 Ví dụ về phân tích đệ quy long f(int n) { if( n <= 1 ) return 1; else return 1 + f(n-1); } Viết biểu thức đệ quy: t(1) = 1 t(n) = 3 + t(n - 1) Liên tục thay thế và phát hiện quy luật: 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)