Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện. Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu tồn tại các hằng C, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”) Ví dụ 1-5: T(n)= (n+1)2 có tỷ suất tăng là n2 nên T(n)= (n+1)2 là O(n2) Chú ý:. | Giải thuật Kĩ thuật phân tích giải thuật Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiện. Cho một hàm T n T n gọi là có độ phức tạp f n nếu tồn tại các hằng C N0 sao cho T n Cf n với mọi n N0 tức là T n có tỷ suất tăng là f n và kí hiệu T n là O f n đọc là ô của f n Ví dụ 1-5 T n n 1 2 có tỷ suất tăng là n2 nên T n n 1 2 là O n2 Chú ý O n O f n với C là hằng số. Đặc biệt O C O 1 Nói cách khác độ phức tạp tính toán của giải thuật là một hàm chặn trên của hàm thời gian. Vì hằng nhân tử C trong hàm chặn trên không có ý nghĩa nên ta có thể bỏ qua vì vậy hàm thể hiện độ phức tạp có các dạng thường gặp sau log2n n nlog2n n2 n3 2n n nn. Ba hàm cuối cùng ta gọi là dạng hàm mũ các hàm khác gọi là hàm đa thức. Một giải thuật mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện còn các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật. Vì ký hiệu log2n thường có mặt trong độ phức tạp nên trong khôn khổ tài liệu này ta sẽ dùng logn thay thế cho log2n với mục đích duy nhất là để cho gọn trong cách viết. Khi nói đến độ phức tạp của giải thuật là ta muốn nói đến hiệu quả của thời gian thực hiện của chương trình nên ta có thể xem việc xác định thời gian thực hiên của chương trình chính là xác định độ phức tạp của giải thuật. CÁCH TÍNH ĐỘ PHỨC TẠP Cách tính độ phức tạp của một giải thuật bất kỳ là một vấn đề không đơn giản. Tuy nhiên ta có thể tuân theo một số nguyên tắc sau Qui tắc cộng Nếu T1 n và T2 n là thời gian thực hiện của hai đoạn chương trình P1 và P2 và T1 n O f n T2 n O g n thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T n O max f n g n Ví dụ 1-6 Lệnh gán x 15 tốn một hằng thời gian hay O 1 Lệnh đọc dữ liệu READ x tốn một hằng thời gian hay O 1 .Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O max 1 1 O 1 Qui tắc nhân Nếu T1 n và T2 n là thời gian thực
