Cấu trúc dữ liệu và giải thuật 2008-2009 - Bài 3: Độ phức tạp thuật toán

ðộ phức tạp thuật toán Lê Sỹ Vinh Bộ môn Khoa Học Máy Tính – Khoa CNTT ðại Học Công Nghệ - ðHQGHN Email: vinhioi@yahoo.com Các vấn ñề liên quan ñến thuật toán 1. Một vấn ñề ñược giải quyết bởi nhiều thuật toán khác nhau 2. ðối với một thuật toán: – ðộ phức tạp về không gian (dung lượng bộ nhớ sử dụng) – ðộ phức tạp về thời gian chạy 3. ðộ phức tạp về thời gian chạy – Kĩ năng lập trình – Chương trình dịch – Tốc ñộ thực hiện các phép toán trên máy tính – Dữ liệu vào “Thời gian chạy chương trình : 10s” ??? ðộ phức tạp thuật toán 1. Thời gian chạy 1 thuật toán phụ thuộc vào cỡ (size) của dữ liệu vào – Tìm xem 1 ñối tượng có trong danh sách N phần tử hay không? – Sắp xếp tăng dần dãy số gồm N số – Bài toán người bán hàng cần thăm N ñịa ñiểm 2. Trong các dữ liệu vào cùng một cỡ (N), thời gian chạy của thuật toán cũng thay ñổi Ví dụ: Tìm xem 1 ñối tượng có trong danh sách N phần tử hay không? – ðối tượng nằm ở ñầu danh sach – ðối tượng nằm ở giữa danh sach – ðối tượng nằm ở cuối danh sách ðộ phức tạp thuật toán 1. Thời gian chạy trong trường hợp xấu nhất (worse-case running time) Thời gian chạy lớn nhất của thuật toán ñó trên tất cả các dữ liệu cùng cỡ 2. Thời gian chạy trung bình Là trung bình cộng thời gian chạy trên tất cả các bộ dữ liệu cùng cỡ. 3. Thời gian chạy trong trường hợp tốt nhất (best-case running time) Thời gian chạy ít nhất của thuật toán ñó trên tất cả các dữ liệu cùng cỡ ðộ phức tạp thuật toán ðánh giá thời gian chạy thuật toán: – T(n) = số lượng phép toán sơ cấp cần phải thực hiện (phép toán số học, phép toán logic, phép toán so sánh). Mỗi phép toán sơ cấp ñược thực hiện trong một khoảng thời gian cố ñịnh. – Quan tâm ñến tốc ñộ tăng của hàm T(n) . – Ví dụ: T(n) = 2n2 + 3n + 10 Biểu diễn thời gian chạy bởi kí hiệu O ðịnh nghĩa. Giả sử f(n) và g(n) là các hàm thực không âm của ñối số nguyên không âm n. Ta nói “f(n) là ô lớn của g(n)” và viết là f(n) = O( g(n) ) nếu tồn tại các hằng số dương c* và n0 sao cho f(n) = n0. Biểu diễn thời gian chạy bởi kí hiệu O Ví dụ. Giả sử f(n) = 5n3 + 2n2 + 13n + 6 , ta có: f(n) = 5n3 + 2n2 + 13n + 6 <= 5n3 + 2n3 + 13n3 + 6n3 = 26n3 f(n) = O(n3) Tổng quát nếu f(n) là một ña thức bậc k của n: f(n) = aknk + ak-1nk-1 + ... + a1n + a0 thì f(n) = O(nk) Ký hiệu ô lớn Tên gọi O(1) O(logn) hằng logarit Biểu diễn thời gian chạy bởi kí hiệu O O(n) O(nlogn) O(n2) O(n3) O(2n) tuyến tính nlogn bình phương lập phương mũ Thời gian chạy của các lệnh 1. Lệnh gán X = Thời gian chạy của lệnh gán bằng thời gian thực hiện biểu thức 2. Lệnh lựa chon if (ñiều kiện) → T0(n) lệnh 1 → T1(n) else lệnh 2 → T2(n) Thời gian: T0(n) + max (T1(n), T2(n)) Thời gian chạy của các lệnh 3. Lệnh lặp: for, while, do-while Ví dụ: ( ) ( )( )∑ + )( 0 nX i nTnT =1i X(n): Số vòng lặp T0(n): ðiều kiện lặp Ti(n): Thời gian thực hiện vòng lặp thứ i Thời gian chạy của các lệnh 4. Phân tích các hàm ñệ quy Ví dụ 2 Thuật toán tạo ra ma trận ñơn vị A cấp n. (1) for (i = 0 ; i < n ; i++) (2) for (j = 0 ; j < n ; j++) (3) A[i][j] = 0; (4) for (i = 0 ; i < n ; i++) (5) A[i][i] = 1; ðộ phức tạp: Ví dụ 3 1) sum = 0; 2) for ( i = 0; i < n; i + +) 3) for ( j = i + 1; i < = n; j + +) 4) for ( k = 1; k < 10; k + +) 5) { sum = sum + i * j * k }; ðộ phức tạp: Ví dụ 4 Phân tích ñộ phức tạp thuật toán của tất cả các phép toán trên kiểu danh dữ liệu danh sách ñược cài ñặt bằng mảng và danh sách liên kết