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

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST

Báo xấu

91
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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: Ví dụ 3: for (i=0; i
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 cg(n) f(n) f(n) bị chặn trên bởi g(n) theo nghĩa tiệm cận n0
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
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
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 + … + 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í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; 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 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)
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