Thuật toán: Độ phức tạp và tính đúng đắn

Với mỗi thuật toán số phép toán cần thực hiện sẽ là mộthàm số theo kích thước đầu vào. Chúng ta sẽ đánh giátính hiệu quả của mỗi thuật toán bằng cách khảo sát độtăng của hàm này.Định nghĩa:Cho f(x) và g(x) là hai hàm số từ tập các số nguyênhoặc số thực đến tập các số thực. Ta nói f(x) là O(g(x))hoặc f(x) là big-O của g(x) hay f(x) Î O(g(x)) nếu tồn tạihai hằng số C và k sao cho...
Nội dung trích xuất từ tài liệu:
Thuật toán: Độ phức tạp và tính đúng đắn Discrete Mathematics IGiới thiệuĐộ tăng hàm Big-O Thuậtt toán Thuậ toán Tính chất Big-Theta Algorithm Tính chất Algorithm Little-oĐộ phức tạp Xấu nhất độ phức ttạp & tính độ phức ạp & tính Trung bình đúng đắn đúng đắnTính đúng đắn complexity & correctness Điều kiện complexity & correctness Lặp Chương 2.2, 2.3 Kenneth H. Rosen Ví d ụTóm tắt Xuân 2008 Đại học FPT 13/12/12 Tổ toán đại học FPT 1/35 Thuật toán GIỚI THIỆU Algorithm INTRODUCTIONGiới thiệuĐộ tăng hàm Big-O Tính chất Chúng ta sẽ học: Big-Theta Tính chất •Đánh giá về độ tăng của hàm Little-o •Big-O, big-ThetaĐộ phức tạp Xấu nhất •Độ phức tạp thuật toán: Độ phức tạp thời gian Trung bìnhTính đúng đắn •Trường hợp xấu nhất Điều kiện Lặp •Trường hợp trung bình Ví d ụ •Tính đúng đắn thuật toánTóm tắt 13/12/12 Tổ toán đại học FPT 2/35 Thuật toán BIG-O Algorithm BIG-OGiới thiệu Với mỗi thuật toán số phép toán cần thực hiện sẽ là mộtĐộ tăng hàm hàm số theo kích thước đầu vào. Chúng ta sẽ đánh giá Big-O Tính chất tính hiệu quả của mỗi thuật toán bằng cách khảo sát độ Big-Theta tăng của hàm này. Tính chất Little-oĐộ phức tạp Địịnhnghĩa Đnh nghĩa Definition Definition Xấu nhất Trung bình Cho f((x)và g((x)là hai hàm số ttừttậpcác số nguyên Cho f x) và g x) là hai hàm số ừ ập các số nguyênTính đúng đắn hoặc số thực đến ttậpcác số thực. Ta nói f((x)là O((g(x)) hoặc số thực đến ập các số thực. Ta nói f x) là O g(x)) Điều kiện hoặc f((x)là big-O của g((x)hay f((x)∈ O((g(x))nếu ttồnttại hoặc f x) là big-O của g x) hay f x) ∈ O g(x)) nếu ồn ại Lặp hai hằng số C và k sao cho Ví d ụ hai hằng số C và k sao choTóm tắt |f((x)|≤ C|g((x)|với imọi ix ≥ k.. |f x)| ≤ C|g x)| vớ mọ x ≥ k Ta sẽ chỉ xét các hàm dương nên sẽ bỏ dấu | | 13/12/12 Tổ toán đại học FPT 3/35 Thuật toán BIG-O Algorithm BIG-OGiới thiệu Ví dụ ExampleĐộ tăng hàm Chứng minh f(n) = 30n + 8 là big-O của g(n) = n. Big-O Tính chất Ta cần chứng minh ∃ c,k: ∀n > k: 30n + 8 ≤ cn. Big-Theta Tính chất cn = Little-o Lấy c = 31, k = 8. Khi đó 31n 30n+8Độ phức tạp với n > k = 8, Xấu nhất cn = 31n = 30n + n > 30n+8 Trung bìnhTính đúng đắn Giá trị cụ thể của c và k Điều kiện n Lặp gọi là bằng chứng. Ta có Ví d ụ thể tìm nhiều bằng chứng.Tóm tắt Chẳng hạn: n>k=8 → c = 32, k = 9 30n+8 ∈O(n) 13/12/12 Tổ toán đại học FPT 4/35 Thuật toán BIG-O Algorithm BIG-OGiới thiệu Khái niệm big-O được sử dụng để đánh giá số phép toánĐộ tăng hàm cần dùng để giải một bài toán theo một thủ tục hoặc một Big-O thuật toán cụ thể. Các hàm số cơ bản thường được dùng Tính chất mũ để so sánh là: Big-Theta Tính chất 1, log(log(n)), log(n), logk(n), n1/k, n, nlog(n), ...