Chương I: Phân tích thuật toán

Một số vấn đề trong việc phân tích thuật toán
Phân tích thời gian thực hiện thuật toán
1. Một số vấn đề trong việc phân tích thuật toán

Tính đúng đắn
Tính đơn giản
Tính tối ưu:
Không gian nhớ
Thời gian
2. Phân tích thời gian thực hiện thuật toán

Phụ thuộc vào nhiều yếu tố:
Phần cứng
Chương trình dịch
Kích thước dữ liệu vào: Nếu gọi n là kích thước dữ liệu vào thì thời gian thực hiện một thuật toán, ký hiệu là T(n) (Độ phức tạp tính toán của thuật toán)
Độ phức tạp tính toán của thuật toán
Ví dụ: Nếu thời gian thực hiện một thuật toán là T(n) = Cn2 (C: hằng dương), thì độ phức tạp tính toán của thuật toán này ký hiệu: T(n) = O(n2).
Tổng quát: Nếu C>0 và n0 sao cho:
T(n)  Cg(n) khi n  n0
thì độ phức tạp của thuật toán:
T(n) = O(g(n))
Xác định độ phức tạp của thuật toán
Quy tắc tổng:
Nếu T1(n) = O(g1(n)) và T2(n) = O(g2(n)) là độ phức tạp của P1 và P2, thì độ phức tạp của “chạy P1 xong chạy P2”:
T(n) = T1(n)+T2(n) = O(max(g1(n), g2(n)))
Tính chất: Nếu g1(n)  g2(n), n  n0 thì:
O(g1(n) + g2(n)) = O(g2(n))
Quy tắc nhân:
Nếu T1(n) = O(g1(n)) và T2(n) = O(g2(n)) là độ phức tạp của P1 và P2, thì độ phức tạp của “P1 lồng P2”:
T(n) = T1(n)T2(n) = O(g1(n)g2(n))
Tính chất:
O(Cg(n)) = O(g(n)), với C là hằng
Phép toán tích cực
Là một phép toán trong thuật toán mà thời gian thực hiện nó không ít hơn thời gian thực hiện các phép khác.
Một phương pháp xác định độ phức tạp tính toán của một thuật toán:
Xác định một phép toán tích cực
Xác định g(n): số lần thực hiện của phép đó
Kết luận: O(g(n)) là độ phức tạp tính toán của thuật toán.
T(n) phụ thuộc vào đặc điểm của dữ liệu
T(n) trong trường hợp thuận lợi nhất: Ttốt
T(n) trong trường hợp xấu nhất: Txấu
T(n) trung bình: Ttb