1. Sự cần thiết phải phân tích, đánh giá giải thuật

Cần phải phân tích, đánh giá giải thuật để:

§         Lựa chọn một giải thuật tốt nhất trong các giải thuật để cài đặt chương trình giải quyết bài toán đặt ra.

§         Cải tiến giải thuật hiện có để được một giải thuật tốt hơn.

2. Tiêu chuẩn đánh giá một giải thuật là tốt

Một giải thuật được xem là tốt nếu nó đạt các tiêu chuẩn sau:

§         Thực hiện đúng.

§         Tốn ít bộ nhớ.

§         Thực hiện nhanh.

3. Thời gian thực hiện của chương trình

Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.

Ví dụ : Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số.

Thời gian thực hiện chương trình là một hàm không âm, tức là T(n) >= 0 V n >= 0.

4. Ðơn vị đo thời gian thực hiện

Ðơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây… mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng.

Ví dụ: Khi ta nói thời gian thực hiện của một chương trình là T(n) = Cn thì có nghĩa là chương trình ấy cần Cn chỉ thị thực thi.

5. Thời gian thực hiện trong trường hợp xấu nhất

Nói chung thì thời gian thực hiện chương trình không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Nghĩa là dữ liệu vào có cùng kích thước nhưng thời gian thực hiện chương trình có thể khác nhau. Chẳng hạn chương trình sắp xếp dãy số nguyên tăng dần, khi ta cho vào dãy có thứ tự thì thời  gian thực hiện khác với khi ta cho vào dãy chưa có thứ tự, hoặc khi ta cho vào một dãy đã có thứ tự tăng thì thời gian thực hiện cũng khác so với khi ta cho vào một dãy đã có thứ tự giảm.

Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là  thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.

6. Tỷ suất tăng

Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số C và N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0.

Ta có thể chứng minh được rằng “Cho một hàm không âm T(n) bất kỳ, ta luôn tìm được tỷ suất tăng f(n) của nó”.

Ví dụ 1: Giả sử T(0) = 1, T(1) = 4 và tổng quát T(n) = (n+1)2. Ðặt N0 = 1 và C = 4 thì với mọi n ≥1 chúng ta dễ dàng chứng minh được rằng T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của  T(n) là  n2.

Ví dụ 2: Tỷ suất tăng của hàm T(n) = 3n3 + 2n2 là n3. Thực vậy, cho N0 = 0 và C = 5 ta dễ dàng chứng minh rằng với mọi n ≥ 0  thì 3n3 + 2n2 ≤ 5n3

7. Khái niệm độ phức tạp của giải thuật

Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n(với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3). Khi n>20 thì T1 < T2. Sở dĩ như vậy là do tỷ suất tăng của T1 nhỏ hơn tỷ suất tăng của T2.

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)”)

Chú ý: O(C.f(n))=O(f(n)) với C là hằng số. Ðặc biệt O(C)=O(1)

Các 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, 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.

Trong cách viết, ta thường dùng logn thay thế cho log2n cho gọn.

8. Phương pháp tính độ phức tạp

Chúng ta sẽ nói đến phương pháp tính độ phức tạp (thời gian thực hiện) của:

§         Chương trình không gọi chương trình con.

§         Chương trình có gọi chương trình con không đệ quy.

§         Chương trình đệ quy

Trước hết ta có hai quy tắc quan trọng là quy tắc cộng và quy tắc nhân

Quy 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))).

Quy tắc nhân:

Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và 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 đoạn chương trình đó lồng nhau là T(n) = O(f(n).g(n)).

9. Qui tắc tổng quát để phân tích một chương trình không có chương trình con

§         Thời gian thực hiện của mỗi lệnh gán, READ, WRITE là O(1)

§         Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi các lệnh.

§         Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1).

§         Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.

 10. Phân tích các chương trình đệ qui

Có thể thấy hình ảnh chương trình đệ quy A như sau:

Với phương pháp tính độ phức tạp của chương trình có gọi chương trình con không đệ qui đã trình bày thì không thể thực hiện được. Bởi vì nếu theo phương pháp đó, để tính thời gian thực hiện của chương trình A, ta phải tính thời gian thực hiện của chương trình A và cái vòng luẩn quẩn ấy không thể kết thúc được.

Để phân tích các các chương trình đệ quy ta cần:

§         Thành lập phương trình đệ quy.

§         Giải phương trình đệ quy, nghiệm của phương trình đệ quy sẽ là thời gian thực hiện của chương trình đệ quy.

11. Thành lập phương trình đệ quy

Phương trình đệ quy là một phương trình biểu diễn mối liên hệ giữa T(n) và T(k), trong đó T(n) và T(k) là thời gian thực hiện chương trình có kích thước dữ liệu nhập tương ứng là n và k, với k < n.

Ðể thành lập được phương trình đệ quy, ta phải căn cứ vào chương trình đệ quy.

Ứng với trường hợp đệ quy dừng, ta phải xem xét khi đó chương trình làm gì và tốn hết bao nhiêu thời gian, chẳng hạn thời gian này là c(n). Khi đệ quy chưa dừng thì phải xét xem có bao nhiêu lời gọi đệ quy với kích thước k ta sẽ có bấy nhiêu T(k). Ngoài ra ta còn phải xem xét đến thời gian để phân chia bài toán và tổng hợp các lời giải, chẳng hạn thời gian này là d(n).

Dạng tổng quát của một phương trình đệ quy sẽ là:

 

Trong đó C(n) là thời gian thực hiện chương trình ứng với trường hợp đệ quy dừng. F(T(k)) là một đa thức của các T(k). d(n) là thời gian để phân chia bài toán và tổng hợp các kết quả.

12. Giải phương trình đệ quy

Có ba phương pháp giải phương trình đệ quy:

§         Phương pháp truy hồi.

§         Phương pháp đoán nghiệm.

§         Lời giải tổng quát của một lớp các phương trình đệ quy.

+ Phương pháp truy hồi

Dùng đệ quy để thay thế bất kỳ T(m) với m < n vào phía phải của phương trình cho đến khi tất cả T(m) với m > 1 được thay thế bởi biểu thức của các T(1) hoặc T(0). Vì T(1) và T(0) luôn là hằng số nên chúng ta có công thức của T(n) chứa các số hạng chỉ liên quan đến n và các hằng số. Từ công thức đó ta suy ra nghiệm của phương trình.

+ Phương pháp đoán nghiệm

Ta đoán một nghiệm f(n) và dùng chứng minh quy nạp để chứng tỏ rằng T(n) ≤ f(n) với mọi n.

Thông thường f(n) là một trong các hàm quen thuộc như logn, n, nlogn, n2, n3, 2n, n!, nn.

Ðôi khi chúng ta chỉ đoán dạng của f(n) trong đó có một vài tham số chưa xác định (chẳng hạn f(n) = an2 với a chưa xác định) và trong quá trình chứng minh quy nạp ta sẽ suy diễn ra giá trị thích hợp của các tham số.

+ Lời giải tổng quát cho một lớp các phương trình đệ quy

Trong mục này, chúng ta sẽ nghiên cứu các phần sau:

§         Bài toán đệ quy tổng quát.

§         Thành lập phương trình đệ quy tổng quát.

§         Giải phương trình đệ quy tổng quát.

§         Các khái niệm về nghiệm thuần nhất, nghiệm riêng và hàm nhân.

§         Nghiệm của phương trình đệ quy tổng quát khi d(n) là hàm nhân.

§         Nghiệm của phương trình đệ quy tổng quát khi d(n) không phải là hàm nhân.

13. Các khái niệm về nghiệm thuần nhất, nghiệm riêng và hàm nhân

Trong công thức , số hạng ak = nlogba được gọi là nghiệm thuần nhất (homogeneous solutions).

Nghiệm thuần nhất là nghiệm chính xác khi d(n) = 0 với mọi n. Nói một cách khác, nghiệm thuần nhất biểu diễn thời gian để giải tất cả các bài toán con.

Trong công thức , tổng  được gọi là nghiệm riêng (particular solutions).

Nghiệm riêng biểu diễn thời gian phải tốn để tạo ra các bài toán con và tổng hợp các kết quả của chúng.

Nghiệm của phương trình (1) là MAX(nghiệm riêng, nghiệm thuần nhất).

Một hàm f(n) được gọi là hàm nhân (multiplicative function) nếu f(m.n) = f(m).f(n) với mọi số nguyên dương m và n.

Ví dụ: Hàm f(n) = nk là một hàm nhân, vì f(m.n) = (m.n)k = mk.nk = f(m).f(n).

          Hàm f(n) = logn không phải là một hàm nhân, vì f(n.m) = log(n.m) = logn+logm ¹ logn.logm = f(n).f(m)

14. Ba trường hợp

Trường hợp 1: a > d(b) thì trong công thức (3) ta có ak > [d(b)]k, theo quy tắc lấy độ phức tạp ta có nghiệm riêng là O(ak) = O(nlogba) = nghiệm thuần nhất. Do đó T(n) là O(nlogba).

Để cải tiến giải thuật, ta cần giảm a hoặc tăng b.

Trường hợp 2: a < d(b) thì trong công thức (3) ta có [d(b)]k > ak, theo quy tắc lấy độ phức tạp ta cónghiệm riêng là O([d(b)]k) = O(nlogbd(b)) > nghiệm thuần nhất. Do đó T(n) là O(nlogbd(b)).

Ðể cải tiến giải thuật chúng ta cần giảm d(b) hoặc tăng b.

Trường hợp 3: a = d(b) thì công thức (3) không xác đinh nên ta phải tính trực tiếp nghiệm riêng:

Do n = bk nên k = logbn và ak = nlogba. Vậy nghiệm riêng là nlogbalogbn > nghiệm thuần nhất. Do đó T(n) là O(nlogbalogbn).