3. Xác định độ phức tạp tính toán của giải thuật
Việc xác định độ phức tạp tính toán của một giải thuật bất kỳ có thể rất phức tạp. Tuy nhiên, độ phức tạp tính toán của một số giải thuật trong thực tế có thể tính bằng một số quy tắc đơn giản.
3.1 Quy tắc bỏ hằng số
Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(c1.f(n)) với c1 là một hằng số dương thì có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(f(n)).
Chứng minh:
T(n) = O(c1.f(n)) nên ∃ c0 > 0 và ∃ n0 > 0 để T(n) ≤ c0.c1 .f(n) với ∀n ≥ n0 . Đặt C = c0.c1 và dùng định nghĩa, ta có T(n) = O(f(n)).
Qui tắc này cũng đúng với các ký pháp Ω, Θ, ο và ω.
3.2 Quy tắc lấy MAX
Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(f(n) + g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp tính toán O(max ( f(n) , g(n) )).
Chứng minh:
T(n) = O(f(n) + g(n)) nên ∃C > 0 và ∃ n0 > 0 để T(n) ≤ C.f(n) + C.g(n), ∀n ≥ n0 .
Vậy T(n) ≤ C.f(n) + C.g(n) ≤ 2C.max(f(n), g(n)) (∀n ≥ n0 ).
Từ định nghĩa suy ra T(n) = O(max( f(n), g(n) )).
Qui tắc này cũng đúng với các ký pháp Ω, Θ, ο và ω.
3.3 Quy tắc cộng
Nếu đoạn chương trình P1 có thời gian thực hiện T1(n) = O(f(n)) và đoạn chương trình P2 có thời gian thực hiện là T2(n) = O( g(n)) thì thời gian thực hiện P1 rồi đến P2 tiếp theo sẽ là:
T1(n) + T2(n) = O(f(n) + g(n))
Chứng minh:
T1(n) = O(f(n)) nên ∃ n1 > 0 và c1 > 0 để T1(n) ≤ c1.f(n) với ∀ n ≥ n1.
T2(n) = O(g(n)) nên ∃ n2 > 0 và c2 > 0 để T2(n) ≤ c2.g(n) với ∀ n ≥ n2.
Chọn n0 = max(n1, n2) và c = max(c1, c2) ta có:
Với ∀ n ≥ n0 :
T1(n) + T2(n) ≤ c1.f(n) + c2.g(n) ≤ c.f(n) + c.g(n) ≤ c.(f(n) + g(n))
Vậy T1(n) + T2(n) = O(f(n) + g(n)).
- Quy tắc cộng cũng đúng với các ký pháp Ω, Θ, ο và ω.
3.4 Quy tắc nhân
Nếu đoạn chương trình P có thời gian thực hiện là T(n) = O( f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O( g(n)) thì độ phức tạp tính toán sẽ là O( g(n). f(n))
Chứng minh
Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n)T(n). Theo định nghĩa.
∃ ck ≥ 0 và nk> 0 để k(n) ≤ ck(g(n)) với ∀ n ≥ nk
∃ cT ≥ 0 và nT > 0 để T(n) ≤ cT (f(n)) với ∀ n ≥ nT
Vậy với ∀ n ≥ max(nT , nk ) ta có k(n).T(n) ≤ cT.ck(g(n).f(n))
- Quy tắc nhân cũng đúng với các ký pháp Ω, Θ, ο và ω.
3.5 Định lý Master (Master Theorem)
Cho a ≥ 1 và b >1 là hai hằng số, f(n) là một hàm với đối số n, T(n) là một hàm xác định trên tập các số tự nhiên được định nghĩa như sau:
T(n) = a.T(n/b) + f(n)
Ở đây n/b có thể hiểu là [n/b]. Khi đó:
- Định lý Master là một định lý quan trọng việc phân tích độ phức tạp tính toán của các giải thuật lặp hay đệ quy. Tuy nhiên việc chứng minh định lý khá dài dòng nằm ngoài phạm vi bài viết này.
3.6 Một số tính chất
- Ta quan tâm chủ yếu đến các ký pháp “lớn”. Rõ ràng ký pháp Θ là “chặt” hơn ký pháp O và Ω theo nghĩa: nếu độ phức tạp tính toán của giải thuật có thể viết là Θ( f(n)) thì cũng có thể viết là O( f(n)) cũng như Ω( f(n)). Dưới đây là một số cách biểu diễn độ phức tạp tính toán qua ký pháp Θ.
Nếu một thuật toán có thời gian thực hiện là P(n), trong đó P(n) là một đa thức bậc k thì độ phức tạp tính toán đó có thể viết là Θ(nk ).
Nếu một thuật toán có thời gian thực hiện là logaf(n). Với b là một số dương, ta nhận thấy logaf(n) = logab.logb f(n). Tức là: Θ(loga f(n)) = Θ(logb f(n)). Vậy ta có thể nói rằng độ phức tạp tính toán của thuật toán đó là Θ(log (f(n))) mà không cần ghi cơ số của logarit.
Nếu một thuật toán có độ phức tạp là hằng số, tức là thời gian thực hiện không phụ thuộc vào kích thước dữ liệu vào thì ta ký hiệu độ phức tạp tính toán của thuật toán đó là Θ(1).
- Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán và bảng giá trị chúng để tiện theo dõi sự tăng của hàm theo đối số n.
- Ví dụ: Thuật toán tính tổng các số từ 1 đến n.
+ Nếu viết theo sơ đồ sau:
Đoạn chương trình ở các dòng 1, 2 và 4 có độ phức tạp tính toán là Θ(1). Vòng lặp ở dòng 3 lặp n lần phép gán S := S + i , nên thời gian tính toán tỉ lệ thuận với n. Tức là độ phức tạp tính toán là Θ(n). Dùng quy tắc cộng và quy tắc lấy max ta suy ra độ phức tạp tính toán của giải thuật trên là Θ(n).
+ Còn nếu viết theo sơ đồ sau:
Độ phức tạp tính toán trong trường hợp này là Θ(1), thời gian tính toán không phụ thuộc vào n.
3.7 Phép toán tích cực
- Dựa vào những nhận xét đã nêu ở trên về các quy tắc khi đánh giá thời gian thực hiện giải thuật, ta chú ý đặc biệt đến một phép toán mà ta gọi là phép toán tích cực trong một đoạn chương trình. Đó là một phép toán trong một đoạn chương trình mà số lần thực hiện không ít hơn các phép toán khác.
- Xét 2 đoạn chương trình tính ex bằng công thức gần đúng:
