Thông thường khi tính toán độ phức tạp của một thuật giải thì thời gian thực hiện là khía cạnh quan trọng của một giải thuật. Việc chọn một giải thuật đưa đến kết quả nhanh nhất là một đòi hỏi thực tế. Thời gian thực hiện giải thuật bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố. Bài viết này sẽ giúp các bạn biết một số khái niệm các các phân tích, đánh giá độ phức tạp của một thuật toán.
1. Giới thiệu (Introduction)
- Như chúng ta được biết thì thời gian thực hiện của giải thuật phụ thuộc vào rất nhiều yếu tố. Trong đó yếu tố cần chú ý nhất là kích thước của dữ liệu đưa vào. Dữ liệu càng lớn thì thời gian xử lý càng chậm. Chẳng hạn như thời gian sắp xếp một dãy số phải chịu ảnh hưởng của các số thuộc dãy số đó. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực hiện của giải thuật có thể biểu diễn một cách tương đối như một hàm của n: T(n).
- Phần cứng máy tính, ngôn ngữ viết chương trình và chương trình dịch ngôn ngữ ấy đều ảnh hưởng tới thời gian thực hiện. Những yếu tố này không giống nhau trên các loại máy vì vậy không thể dựa vào chúng khi xác định T(n) => T(n) không thể biểu diễn bằng đơn vị thời gian (giờ, phút, giây..).
- Nếu thời gian thực hiện một giải thuật là T1(n) = n^2 (n mũ 2) và thời gian thực hiện của một giải thuật khác là T2(n) = 100n thì khi n đủ lớn thời gian thực hiện của giải thuật T2 rõ ràng nhanh hơn T1. Khi đó, nếu nói rằng thời gian thực hiện giải thật tỉ lệ thuận với n hay tỉ lệ thuận với n2 cũng cho ta một cách đánh giá tương đối về tốc độ thực hiện của giải thuật đó khi n khá lớn.
- Cách đánh giá thời gian thực hiện của giải thuật độc lập với máy tính và các yếu tố liên quan tới máy tính như vậy sẽ dẫn tới khái niệm gọi là độ phức tạp của giải thuật.
2. Các ký pháp để đánh giá độ phức tạp tính toán.
Cho một giải thuật thực hiện trên dữ liệu với kích thước n. Giả sử T(n) là thời gian thực hiện một giải thuật đó, g(n) là một hàm xác định dương với mọi n. Khi đó ta nói độ phức tạp tính toán của giải thuật là:
- O(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho T(n) ≤ c.g(n) với mọi n ≥ n0 . Ký pháp này được gọi là ký pháp chữ O lớn (big-oh notation). Trong ký pháp chữ O lớn, hàm g(.) được gọi là giới hạn trên (asymptotic upper bound) của hàm T(.).
- Ω(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho c.g(n) ≤ T(n) với mọi n ≥ n0. Ký hiệu này gọi là ký pháp Ω lớn (big-omega notation). Trong ký pháp Ω lớn, hàm g(.) được gọi là giới hạn dưới (asymptotically lower bound) của hàm T(.).
- Θ(g(n) nếu tồn tại các hằng số dương c1, c2 và n0 sao cho c1.g(n) ≤ f(n) ≤ c2.g(n) với mọi n ≥ n0 . Ký pháp này được gọi là ký pháp Θ lớn (big-theta notation). Trong ký pháp Θ lớn, hàm g(.) được gọi là giới hạn chặt (asymptotically tight bound) của hàm T(.).
Hình dưới đây: biểu diễn đồ thị của ký pháp Θ lớn, Ο lớn và Ω lớn. Dễ thấy rằng T(n) = Θ(g(n)) nếu và chỉ nếu T(n) = O(g(n)) và T(n) = Ω(g(n))
- Ta nói độ phức tạp tính toán của giải thuật là:
o(g(n)) nếu với mọi hằng số dương c, tồn tại một hằng số dương n0 sao cho T(n) ≤ c.g(n) với mọi n ≥ n0. Ký pháp này gọi là ký pháp chữ o nhỏ (little-oh notation).
ω(g(n)) nếu với mọi hằng số dương c, tồn tại một hằng số dương n0 sao cho c.g(n) ≤ T(n) với mọi n ≥ n0 . Ký pháp này gọi là ký pháp ω nhỏ (little-omega notation).
- Ví dụ: Nếu T(n) = n2 + 1, thì:
T(n) = O(n2 ). Thật vậy, chọn c = 2 và n0 = 1. Rõ ràng với mọi n ≥ 1, ta có: T(n) = n2 + 1 ≤ 2.n2 = 2.g(n).
T(n) ≠ o(n2). Thật vậy, chọn c = 1. Rõ ràng không tồn tại n để: n2 + 1 ≤ n2 , tức là không tồn tại n0 thoả mãn định nghĩa của ký pháp chữ o nhỏ.
- Lưu ý rằng không có ký pháp θ nhỏ.
Một vài tính chất
- Tính bắt cầu (transitivity): Tất cả các ký pháp nêu trên đều có tính bắt cầu.
Nếu f(n) = Θ(g(n)) và g(n) = Θ(h(n)) thì f(n) = Θ(h(n)).
Nếu f(n) = O(g(n)) và g(n) = O(h(n)) thì f(n) = O(h(n)).
Nếu f(n) = Ω(g(n)) và g(n) = Ω(h(n)) thì f(n) = Ω(h(n)).
Nếu f(n) = o(g(n)) và g(n) = o(h(n)) thì f(n) = o(h(n)).
Nếu f(n) = ω(g(n)) và g(n) = ω(h(n)) thì f(n) = ω(h(n)).
- Tính phản xạ (reflectivity): Các ký pháp “lớn” mới có tính phản xạ.
f(n) = Θ(f(n)).
f(n) = O(f(n)).
f(n) = Ω(f(n)).
- Tính đối xứng (symmetry): chỉ có ký pháp Θ mới có tính đối xứng.
f(n) = Θ(g(n)) nếu và chỉ nếu g(n) = Θ(f(n)).
- Tính chuyển vị đối xứng (transpose symmetry):
f(n) = O(g(n)) nếu và chỉ nếu g(n) = Ω(f(n)).
f(n) = o(g(n)) nếu và chỉ nếu g(n) = ω(f(n)).
Để dễ nhớ ta coi các ký pháp Ο, Ω, Θ, ο, ω lần lượt tương ứng với các phép so sánh ≤, ≥, =, <, >. Từ đó suy ra các tính chất trên.