Với mỗi thuật toán số phép toán cần thực hiện sẽ là một hà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 nghĩa: Cho f(x) và g(x) là hai hàm số từ tập các số nguyên hoặ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ại hai hằng số C và k sao cho. | 5/14/2020 1:09:52 AM Chương , Kenneth H. Rosen Xuân 2008 Đại học FPT Discrete Mathematics I độ phức tạp & tính đúng đắn complexity & correctness Thuật toán Algorithm 5/14/2020 1:09:52 AM Thuật toán GIỚI THIỆU Algorithm INTRODUCTION Giới thiệu Chúng ta sẽ học: Đánh giá về độ tăng của hàm Big-O, big-Theta Độ phức tạp thuật toán: Độ phức tạp thời gian Trường hợp xấu nhất Trường hợp trung bình Tính đúng đắn thuật toán 5/14/2020 1:09:52 AM Thuật toán BIG-O Algorithm BIG-O Định nghĩa Definition Cho f(x) và g(x) là hai hàm số từ tập các số nguyên hoặ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ại hai hằng số C và k sao cho |f(x)| C|g(x)| với mọi x k. Big-O Với mỗi thuật toán số phép toán cần thực hiện sẽ là một hà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. Ta sẽ chỉ xét các hàm dương nên sẽ bỏ dấu | | 5/14/2020 1:09:52 AM Thuật toán . | 5/14/2020 1:10:28 AM Chương , Kenneth H. Rosen Xuân 2008 Đại học FPT Discrete Mathematics I độ phức tạp & tính đúng đắn complexity & correctness Thuật toán Algorithm 5/14/2020 1:10:28 AM Thuật toán GIỚI THIỆU Algorithm INTRODUCTION Giới thiệu Chúng ta sẽ học: Đánh giá về độ tăng của hàm Big-O, big-Theta Độ phức tạp thuật toán: Độ phức tạp thời gian Trường hợp xấu nhất Trường hợp trung bình Tính đúng đắn thuật toán 5/14/2020 1:10:28 AM Thuật toán BIG-O Algorithm BIG-O Định nghĩa Definition Cho f(x) và g(x) là hai hàm số từ tập các số nguyên hoặ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ại hai hằng số C và k sao cho |f(x)| C|g(x)| với mọi x k. Big-O Với mỗi thuật toán số phép toán cần thực hiện sẽ là một hà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. Ta sẽ chỉ xét các hàm dương nên sẽ bỏ dấu | | 5/14/2020 1:10:28 AM Thuật toán BIG-O Algorithm BIG-O Ví dụ Example Chứng minh f(n) = 30n + 8 là big-O của g(n) = n. Ta cần chứng minh c,k: n > k: 30n + 8 cn. Lấy c = 31, k = 8. Khi đó với n > k = 8, cn = 31n = 30n + n > 30n+8 n>k=8 n 30n+8 cn = 31n 30n+8 O(n) Giá trị cụ thể của c và k gọi là bằng chứng. Ta có thể tìm nhiều bằng chứng. Chẳng hạn: c = 32, k = 9 Big-O 5/14/2020 1:10:28 AM giai thừa Thuật toán BIG-O Algorithm BIG-O Khái niệm big-O được sử dụng để đánh giá số phép toán cần dùng để giải một bài toán theo một thủ tục hoặc một thuật toán cụ thể. Các hàm số cơ bản thường được dùng để so sánh là: 1, log(log(n)), log(n), logk(n), n1/k, n, nlog(n), nk, an, n!, nn hằng logarit đa thức mũ Big-O 5/14/2020 1:10:28 AM Thuật toán BIG-O Algorithm BIG-O Định lí Theorem anxn + an -1xn -1 + + a1x + a0 O(xn) (a0, a1, , an là các số thực) f O(g) g O(h) f O(h) af, f 1-b, (logbf)a O(f) với mọi a, b R và b 0. f1 O(g1) f2 O(g2) f1 f2 O(g1g2) f1 O(g1) f2 O(g2) f1+f2 O(g1+g2) O(g1+g2) = .
