tailieunhanh - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG I: THUẬT TOÁN_3

Một cách tổng quát, nếu f(n)=aknk+ak-1nk-1+ . +a1n+a0 thì f(n)=O(nk). Thật vậy, với n1, |f(n)|| |ak|nk+|ak-1|nk-1+ . +|a1|n+|a0| = nk(|ak|+|ak-1|/n+ . +|a1|/nk-1+a0/nk) nk(|ak|+|ak-1|+ . +|a1|+a0) | CHƯƠNG I THUẬT TOÁN Thí dụ 5 Hàm f n n 3 là hàm bậc hai và hàm bậc hai đơn giản nhất là n2. Ta có f n n n 3 O n2 vì n n 3 n2 với mọi n 3 C 1 n0 3 . v 2 2 v 0 7 Một cách tổng quát nếu f n aknk ak-1nk-1 . a1n a0 thì f n O nk . Thật vậy với n 1 f n ak nk ak-1 nk-1 . a1 n a0 nk ak ak-1 n . a1 nk-1 a0 nk nk ak ak-1 . a1 a0 . Điều này chứng tỏ f n Cnk với mọi n 1. Cho g n 3n 5nlog2n ta có g n O nlog2n . Thật vậy 3n 5nlog2n n 3 5log2n n log2n 5log2n 6nlog2n với mọi n 8 C 6 n0 8 . Mệnh đề Cho f1 n O g1 n và f2 n là O g2 n . Khi đó f1 f2 n O max g1 n g2 n f1f2 n O g1 n g2 n . Chứng minh. Theo giả thiết tồn tại C1 C2 n1 n2 sao cho f1 n C1 g1 n và f2 n Cz gz n với mọi n n và mọi n n2. Do đó f1 f2 n fi n f2 n fi n f2 n Ci gi n C2 g2 n Ci C2 g n với mọi n n0 max n1 n2 ở đâyC C1 C2 và g n max g1 n g2 n . fif2 n fi n f2 n Ci gi n C2 g2 n CiC2 gig2 n với mọi n no max ni n2 . Định nghĩa 2 Nếu một thuật toán có độ phức tạp là f n với f n O g n thì ta cũng nói thuật toán có độ phức tạp O g n . Nếu có hai thuật toán giải cùng một bài toán thuật toán 1 có độ phức tạp O g1 n thuật toán 2 có độ phức tạp O g2 n mà g1 n có cấp thấp hơn g2 n thì ta nói rằng thuật toán 1 hữu hiệu hơn hay nhanh hơn thuật toán 2. . Đánh giá độ phức tạp của một thuật toán 1 Thuật toán tìm kiếm tuyến tính Số các phép so sánh được dùng trong thuật toán này cũng sẽ được xem như thước đo độ phức tạp thời gian của nó. Ở mỗi một bước của vòng lặp trong thuật toán có hai phép so sánh được thực hiện một để xem đã tới cuối bảng chưa và một để so sánh phần tử x với một số hạng của bảng. Cuối cùng còn một phép so sánh nữa làm ở ngoài vòng lặp. Do đó nếu x ai thì đã có 2i 1 phép so sánh được sử dụng. Số phép so sánh nhiều nhất 2n 2 đòi hỏi phải được sử dụng khi phần tử x không có mặt trong bảng. Từ đó thuật toán tìm kiếm tuyến tính có độ phức tạp là O n . 2 Thuật toán tìm kiếm nhị phân Để đơn giản ta giả sử rằng có n 2k phần tử trong bảng liệt kê ai a2 . an với k là số nguyên không âm nếu n không phải là lũy thừa của