Chương 11 Độ phức tạp (complexity)

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level 19/09/2013 ‹#› /XX MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH ĐỘ PHỨC TẠP(Complexity) Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.edu.vn CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Khái niệm Thuật toán (Algorithm) là một dãy hữu hạn các bước có thể thực thi được mà theo đó ta đạt được lời giải của bài toán. Từ Algorithm bắt nguồn từ nhà toán học Ả Rập Al-Khwārizmī Thuật toán giải phương trình bậc 2, thuật toán tìm số lớn nhất trong dãy số, thuật toán sắp xếp… Ví dụ Mô tả giải thuật tìm phần tử lớn nhất trong dãy hữu hạn các phần tử B1: Đặt giá trị cực đại tạm thời (max) là phần tử đầu tiên của dãy B2: Nếu số kế tiếp lớn hơn max thì gán giá trị max = số đó B3: Lặp lại bước 2 nếu còn phần tử trong dãy B4: Dừng khi không còn phần tử trong dãy, số max lúc này là phần tử lớn nhất của dãy Dữ liệu nhập (input) Dữ liệu xuất (output) Dãy thao tác Khái niệm Các tính chất cơ bản của thuật toán Tính xác định (rõ ràng, xác định). Tính hữu hạn (dừng). Tính đúng đắn. Tính tổng quát: phải áp dụng được cho 1 họ các vấn đề Đầu vào Đầu ra Độ phức tạp của thuật toán Độ phức tạp của thuật toán Thời gian (số thao tác) Không gian Dữ liệu nhập Độ phức tạp của thuật toán Thời gian mà máy tính khi thực hiện một thuật toán phụ thuộc vào: Bản thân thuật toán đó. Máy tính đang thực thi thuật toán. Đánh giá hiệu quả của một thuật toán có thể: Xét số các phép tính phải thực hiện khi thực hiện thuật toán này. Độ phức tạp của thuật toán Độ phức tạp về không gian Độ phức tạp về thời gian Độ phức tạp về giải thuật Độ phức tạp về không gian Chiếm tài nguyên của máy Bộ nhớ Sử dụng CPU Băng thông … VD: heap sort nếu dùng heap mà không dùng arraytốn bộ nhớ Độ phức tạp về thời gian Tính hiệu quả của thuật toán được tính bằng phương pháp thực nghiệm thông qua các bộ dữ liệu thử Phụ thuộc vào ngôn ngữ lập trình Trình độ, kỹ năng của người viết Phần cứng máy tính dùng để thử nghiệm Sự phức tạp của việc xây dựng một bộ dữ liệu thử Độ phức tạp về giải thuật Mang tính hình thức Phép đo độc lập với máy tính, ngôn ngữ lập trình, người lập trình hay những tiểu tiết: tăng giảm, chỉ số vòng lặp, sự khởi gán,… Thời gian thực thi của giải thuật sẽ tăng theo kích thước dữ liệu, thời gian này sẽ tỷ lệ các thao tác cơ sở Độ phức tạp thuật toán là một hàm phụ thuộc đầu vào Độ phức tạp của thuật toán Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Trong thực tiễn, chỉ cần biết một ước lượng đủ tốt của chúng. Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm big-O Những thao tác cơ sở Là các phép toán tham gia trực tiếp vào quá trình xử lý Ví dụ Phép so sánh Phép chuyển dời Phép toán số học,.. Trong các giải thuật sắp xếp thì các phép toán cơ sở là so sánh và chuyển dời Độ phức tạp của thuật toán (tt) Thuật toán 1 Thuật toán 2 Thuật toán 3 Dữ liệu nhập Thời gian (số thao tác) Độ phức tạp của thuật toán (tt) Thời gian tối thiểu (trường hợp tốt nhất). Thời gian tối đại (trường hợp xấu nhất). Thời gian trung bình. Ta thường dùng các ký hiệu sau để mô tả cho độ phức tạp thuật toán Bậc big-O: chặn trên, trường hợp tốt nhất Bậc big-Ω: chặn dưới, trường hợp xấu nhất Bậc Θ (bậc Theta): chặn 2 đầu, trung bình Ký hiệu O Cho f, g là 2 hàm thực xác định trong N. Khi đó ta viết f(n) = O(g(n)) Nếu C>0, kN, nN, n≥k  |f(n)| ≤ C.|g(n)| Với n là độ lớn đầu vào: Bài toán giai thừa: n là số cần tính giai thừa Bài toán sai phân: n là số chữ số có nghĩa cần đạt được Các phép tính trên ma trận: n là số hàng hoặc số cột của ma trận Ký hiệu O (tt) 3n = O(15n) do n > 0, 3n  115n. 15n = O(3n) do n > 0, 15n  53n. 3n và 15n đều = O(n)? n2 = O(n3) do n > 1, n2 0, kN sao cho n  k  f(n)  cg(n). (i.e. ). Khi đó g được gọi là tăng nhanh hơn f. Thí dụ Chứng minh rằng: n2 = o(n2logn). Một số lớp độ phức tạp thường gặp Độ phức tạp hằng: O(1). Độ phức tạp logarith: O(logn). Độ phức tạp tuyến tính: O(n). Độ phức tạp nlogn: O(nlogn). Độ phức tạp đa thức: O(nk). Độ phức tạp mũ: O(kn), k>1. Độ phức tạp giai thừa: O(n!). Mức độ tăng trưởng Sắp theo thứ tự tăng dần 1 logn n nlogn nk kn, k>1 n! Mức độ tăng trưởng n logn nlogn n2 n3 2n 1 0 0 1 1 2 2 1 2 4 8 4 3 2 8 16 64 16 8 3 24 64 512 256 16 4 64 256 4096 65536 32 5 160 1024 32768 2147483648 Thời gian thực hiện Độ phức tạp Thời gian O(log(n)) 10-7 giây O(n) 10-6 giây O(nlogn) 10-5 giây O(n2) 10-4 giây O(n3) 3 phút O(2n) 1014 năm O(n!) 10142 năm Một số ví dụ Thuật toán sắp xếp theo phương pháp nổi bọt (bubble sort) /* Sắp xếp theo thứ tự tăng dần */ for (i=1; i=i; j--) if (a[j-1] > a[j]) swap(a[j-1], a[j]); Độ phức tạp: O(n2) Một số ví dụ Thuật toán sắp xếp quicksort void quickSort(int[] a, int left, int right) { int i, j, x; i = left; j = right; x = a[(i+j)/2]; do { while (a[i] < x) i = i + 1; while (x < a[j]) j = j - 1; if (i<=j) { swap(a[i], a[j]); i++; j--; } } while (i<=j); if (left < j) quickSort(left, j); if (i < right) quickSort(i, right); } Một số ví dụ (tt) Sắp xếp dãy 44 55 12 42 94 18 06 67 Độ phức tạp của thuật toán quick sort: O(nlogn). Một số ví dụ (tt) Bài toán tháp Hanoi HỎI ĐÁP