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.
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:
4. Độ phức tạp tính toán với tình trạng dữ liệu vào
Có nhiều trường hợp, thời gian thực hiện giải thuật không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng của dữ liệu đó nữa. Chẳng hạn thời gian sắp xếp một dãy số theo thứ tự tăng dần mà dãy đưa vào chưa có thứ tự sẽ khác với thời gian sắp xếp một dãy số đã sắp xếp rồi hoặc đã sắp xếp theo thứ tự ngược lại. Lúc này, khi phân tích thời gian thực hiện giải thuật ta sẽ xét trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất.
- Phân tích thời gian thực hiện giải thuật trong trường hợp xấu nhất (worst-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian lớn nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện giải thuật dựa trên hàm T(n).
- Phân tích thời gian thực hiện giải thuật trong trường hợp tốt nhất (best-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian ít nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện dựa trên hàm T(n).
- Phân tích thời gian trung bình thực hiện giải thuật (average-case analysis): giả sử rằng dữ liệu vào tuân theo một phân phối xác suất nào đó (chẳng hạn phân bố đều nghĩa là khả năng chọn mỗi bộ dữ liệu vào là như nhau) và tính toán giá trị kỳ vọng (trung bình) của thời gian chạy cho mỗi kích thước dữ liệu n (T(n)), sau đó phân tích thời gian thực hiện giải thuật dựa trên hàm T(n).
Khi khó khăn trong việc độ phức tạp tính toán trung bình (bởi việc xác định T(n) trung bình thường phải dùng tới những công cụ tính toán phức tạp), người ta thường chỉ đánh giá độ phức tạp tính toán trong trường hợp xấu nhất.
Không nên lẫn lộn các cách phân tích trong trường hợp xấu nhất, trung bình, và giá tốt nhất với các ký pháp biểu diễn độ phức tạp tính toán, đây là 2 khái niệm hoàn toàn phần biệt.
Trên phương diện lý thuyết, đánh giá bằng ký pháp Θ(.) là tốt nhất, tuy vậy việc đánh giá bằng ký pháp Θ(.) đòi hỏi phải đánh giá bằng cả ký pháp O(.) lẫn Ω(.). Dẫn tới việc phân tích thuật toán khá phức tạp, gần như phải biểu diễn chính xác thời gian thực hiện giải thuật qua các hàm giải tích. Vì vậy trong những thuật toán người ta thường dùng ký pháp T(n) = O( f(n)).
5. Chi phí thực hiện thuật toán.
- Khái niệm độ phức tạp thuật toán đặt ra không chỉ dùng để đánh giá chi phí thực hiện một giải thuật về mặt thời gian mà là để đánh giá chi phí thực hiện giải thuật nói chung, bao gồm cả chi phí về thời gian ( lượng bộ nhớ cần sử dụng).
- Thông thường:
Nếu ta đánh giá được độ phức tạp tính toán của một giải thuật qua ký pháp Θ, có thể coi phép đánh giá này là chủ chặt và không cần đánh giá qua các ký pháp khác nữa.
Nếu không:
+ Để nhấn mạnh tính “tốt” của một giải thuật, các ký pháp O, o thường được sử dụng. Nếu đánh giá được qua O thì không cần đánh giá qua o. Ý nói: chi phí thực hiện thuật toán tối đa là …, ít hơn….
+ Đề cập đến tính toán “tồi” của một giải thuật, các ký pháp Ω, ω thường được sử dụng. Nếu đánh giá được qua Ω thì không cần đánh giá qua ω. Ý nói chi phí thực hiện thuật toán tối thiểu là…, cao hơn…
- 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.
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:
4. Độ phức tạp tính toán với tình trạng dữ liệu vào
Có nhiều trường hợp, thời gian thực hiện giải thuật không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng của dữ liệu đó nữa. Chẳng hạn thời gian sắp xếp một dãy số theo thứ tự tăng dần mà dãy đưa vào chưa có thứ tự sẽ khác với thời gian sắp xếp một dãy số đã sắp xếp rồi hoặc đã sắp xếp theo thứ tự ngược lại. Lúc này, khi phân tích thời gian thực hiện giải thuật ta sẽ xét trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất.
- Phân tích thời gian thực hiện giải thuật trong trường hợp xấu nhất (worst-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian lớn nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện giải thuật dựa trên hàm T(n).
- Phân tích thời gian thực hiện giải thuật trong trường hợp tốt nhất (best-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian ít nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện dựa trên hàm T(n).
- Phân tích thời gian trung bình thực hiện giải thuật (average-case analysis): giả sử rằng dữ liệu vào tuân theo một phân phối xác suất nào đó (chẳng hạn phân bố đều nghĩa là khả năng chọn mỗi bộ dữ liệu vào là như nhau) và tính toán giá trị kỳ vọng (trung bình) của thời gian chạy cho mỗi kích thước dữ liệu n (T(n)), sau đó phân tích thời gian thực hiện giải thuật dựa trên hàm T(n).
Khi khó khăn trong việc độ phức tạp tính toán trung bình (bởi việc xác định T(n) trung bình thường phải dùng tới những công cụ tính toán phức tạp), người ta thường chỉ đánh giá độ phức tạp tính toán trong trường hợp xấu nhất.
Không nên lẫn lộn các cách phân tích trong trường hợp xấu nhất, trung bình, và giá tốt nhất với các ký pháp biểu diễn độ phức tạp tính toán, đây là 2 khái niệm hoàn toàn phần biệt.
Trên phương diện lý thuyết, đánh giá bằng ký pháp Θ(.) là tốt nhất, tuy vậy việc đánh giá bằng ký pháp Θ(.) đòi hỏi phải đánh giá bằng cả ký pháp O(.) lẫn Ω(.). Dẫn tới việc phân tích thuật toán khá phức tạp, gần như phải biểu diễn chính xác thời gian thực hiện giải thuật qua các hàm giải tích. Vì vậy trong những thuật toán người ta thường dùng ký pháp T(n) = O( f(n)).
5. Chi phí thực hiện thuật toán.
- Khái niệm độ phức tạp thuật toán đặt ra không chỉ dùng để đánh giá chi phí thực hiện một giải thuật về mặt thời gian mà là để đánh giá chi phí thực hiện giải thuật nói chung, bao gồm cả chi phí về thời gian ( lượng bộ nhớ cần sử dụng).
- Thông thường:
Nếu ta đánh giá được độ phức tạp tính toán của một giải thuật qua ký pháp Θ, có thể coi phép đánh giá này là chủ chặt và không cần đánh giá qua các ký pháp khác nữa.
Nếu không:
+ Để nhấn mạnh tính “tốt” của một giải thuật, các ký pháp O, o thường được sử dụng. Nếu đánh giá được qua O thì không cần đánh giá qua o. Ý nói: chi phí thực hiện thuật toán tối đa là …, ít hơn….
+ Đề cập đến tính toán “tồi” của một giải thuật, các ký pháp Ω, ω thường được sử dụng. Nếu đánh giá được qua Ω thì không cần đánh giá qua ω. Ý nói chi phí thực hiện thuật toán tối thiểu là…, cao hơn…
(Theo A.K.A DSAP Textbox)