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

Bài giảng "Cấu trúc dữ liệu và giải thuật: Phân tích thuật toán" cung cấp cho người học các kiến thức: Phân tích độ phức tạp, phân tích độ phức tạp tiệm cận, ký hiệu Ô lớn, ký hiệu Ô-mê-ga lớn, ký hiệu Tê-ta lớn, tính chất bắc cầu, tốc độ tăng của một số hàm cơ bản. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Phân tích thuật toán - Nguyễn Mạnh HiểnPhân tích thuật toánNguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@tlu.edu.vnPhâ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ùngVí dụ đếm số thao tácVí dụ 1: Ví dụ 3:for (i=0; iPhâ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 cg(n) f(n) f(n) bị chặn trên bởi g(n) theo nghĩa tiệm cận n0Ký 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 n0Ký 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) n0Ví 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ácHã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ácTí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 + … + aknk (đ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ínhTố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; nĐộ phức tạp = 1 + max (1, n) =1+n = O(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 ...