Giải thuật và lập trình: §2. Phân tích thời gian thực hiện giải thuật


ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT

Với một bài toán không chỉ có một giải thuật. Chọn một giải thuật đưa tới kết quả nhanh nhất là một đòi hỏi thực tế. Như vậy cần có một căn cứ nào đó để nói rằng giải thuật này nhanh hơn giải thuật kia?

Thời gian thực hiện một 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ố. Một 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 số lượng 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 một 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ức là T(n) không thể biểu diễn bằng đơn vị thời gian giờ, phút, giây được. Tuy nhiên, không phải vì thế mà không thể so sánh được các giải thuật về mặt tốc độ. Nếu như thời gian thực hiện một giải thuật là T1(n) = n2 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 giải thuật T1. Khi đó, nếu nói rằng thời gian thực hiện giải thuậ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 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 tính toán của giải thuật.

Cho f và g là hai hàm xác định dương với mọi n. Hàm f(n) được gọi là O(g(n)) nếu tồn tại một hằng số c > 0 và một giá trị n0 sao cho:

f(n) ≤ c.g(n) với mọi n ≥ n0

Nghĩa là nếu xét những giá trị n ≥ n0 thì hàm f(n) sẽ bị chặn trên bởi một hằng số nhân với g(n). Khi đó, nếu f(n) là thời gian thực hiện của một giải thuật thì ta nói giải thuật đó có cấp là g(n), ký hiệu: O(g(n)) (Ký pháp O(.) được gọi là ký pháp chữ O lớn (big O notation)) hay Θ(g(n)).

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, trong thực tế, đối với một số giải thuật ta có thể phân tích bằng một số quy tắc đơn giản:

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(max(f(n), g(n)))

Chứng minh:

T1(n) = O(f(n)) nên tồn tại n1 và c1 để T1(n) ≤ c1.f(n) với mọi n ≥ n1.

T2(n) = O(g(n)) nên tồn tại n2 và c2 để T2(n) ≤ c2.g(n) với mọi n ≥ n2.

Chọn n0 = max(n1, n2) và c = max(c1, c2) ta có:

Với mọi n ≥ n0:

T1(n) + T2(n) ≤ c1.f(n) + c2.g(n) ≤ c.f(n) + c.g(n) ≤ c.(f(n) + g(n)) ≤ 2c.(max(f(n), g(n))). Vậy, T1(n) + T2(n) = O(max(f(n), g(n))).

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:

Tồn tại ck ≥ 0 và nk để k(n) ≤ ck(g(n)) với mọi n ≥ nk

Tồn tại cT ≥ 0 và nT để T(n) ≤ cT(f(n)) với mọi n ≥ nT

Vậy với mọi n ≥ max(nT, nk) ta có k(n).T(n) ≤ cT.ck(g(n).f(n))

Một số tính chất

Theo định nghĩa về độ phức tạp tính toán ta có một số tính chất:

  1. Với P(n) là một đa thức bậc k thì O(P(n)) = O(nk). Vì thế, một thuật toán có độ phức tạp cấp đa thức, người ta thường ký hiệu là O(nk)
  2. Với a và b là hai cơ số tuỳ ý và f(n) là một hàm dương thì logaf(n) = logab.logbf(n). Tức là: O(logaf(n)) = O(logbf(n)). Vậy với một thuật toán có độ phức tạp cấp logarit của f(n), người ta ký hiệu là O(logf(n)) mà không cần ghi cơ số của logarit.
  3. 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à O(1).
  4. Một giải thuật có cấp là các hàm như 2n, n!, nn được gọi là một giải thuật có độ phức tạp hàm mũ. Những giải thuật như vậy trên thực tế thường có tốc độ rất chậm. Các giải thuật có cấp là các hàm đa thức hoặc nhỏ hơn hàm đa thức thì thường chấp nhận được.
  5. Không phải lúc nào một giải thuật cấp O(n2) cũng tốt hơn giải thuật cấp O(n3). Bởi nếu như giải thuật cấp O(n2) có thời gian thực hiện là 1000n2, còn giải thuật cấp O(n3) lại chỉ cần thời gian thực hiện là n3, thì với n < 1000, rõ ràng giải thuật O(n3) tốt hơn giải thuật O(n2). Trên đây là xét trên phương diện tính toán lý thuyết để định nghĩa giải thuật này "tốt" hơn giải thuật kia, khi chọn một thuật toán để giải một bài toán thực tế phải có một sự mềm dẻo nhất định.
  6. Cũng theo định nghĩa về độ phức tạp tính toán:

Một thuật toán có cấp O(1) cũng có thể viết là O(logn)

Một thuật toán có cấp O(logn) cũng có thể viết là O(n)

Một thuật toán có cấp O(n) cũng có thể viết là O(n.logn)

Một thuật toán có cấp O(n.logn) cũng có thể viết là O(n2)

Một thuật toán có cấp O(n2) cũng có thể viết là O(n3)

Một thuật toán có cấp O(n3) cũng có thể viết là O(2n)

Vậy độ phức tạp tính toán của một thuật toán có nhiều cách ký hiệu, thông thường người ta chọn cấp thấp nhất có thể, tức là chọn ký pháp O(f(n)) với f(n) là một hàm tăng chậm nhất theo n.

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ị của chúng để tiện theo dõi sự tăng của hàm theo đối số n.

log2n

n

nlog2n

n2

n3

2n

0

1

0

1

1

2

1

2

2

4

8

4

2

4

8

16

64

16

3

8

24

64

512

256

4

16

64

256

4096

65536

5

32

160

1024

32768

2147483648

Ví dụ:

Thuật toán tính tổng các số từ 1 tới n: Nếu viết theo sơ đồ như sau:

Input n;

S := 0;

for i := 1 to n do S := S + i;

Output S;

Các đoạn chương trình ở các dòng 1, 2 và 4 có độ phức tạp tính toán là O(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à O(n).

Vậy độ phức tạp tính toán của thuật toán trên là O(n). Còn nếu viết theo sơ đồ như sau:

Input n;

S := n * (n - 1) div 2;

Output S;

Thì độ phức tạp tính toán của thuật toán trên là O(1), thời gian tính toán không phụ thuộc vào n.

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ần chú ý đế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 hai đoạn chương trình tính ex bằng công thức gần đúng:

Công thức tính e mũ x

với x và n cho trước.

Chương trình 1: Tính riêng từng hạng tử rồi cộng lại

{Chương trình 1: Tính riêng từng hạng tử rồi cộng lại}

program Exp1;

var

i, j, n: Integer; x, p, S: Real; begin

Write('x, n = '); ReadLn(x, n); S := 0;

for i := 0 to n do begin

p := 1;

for j := 1 to i do p := p * x / j; S := S + p;

end;

WriteLn('exp(', x:1:4, ') = ', S:1:4);

end.

Ta có thể coi phép toán tích cực ở đây là phép: p := p * x / i.

Số lần thực hiện phép toán này là n.

Vậy độ phức tạp tính toán của thuật toán là O(n).

Tính hạng tử sau qua hạng tử trước

{Tính hạng tử sau qua hạng tử trước}

program Exp2;

var

i, n: Integer;

x, p, S: Real;

begin

Write('x, n = '); ReadLn(x, n);

S := 1; p := 1;

for i := 1 to n do begin

p := p * x / i;

S := S + p;

end;

WriteLn('exp(', x:1:4, ') = ', S:1:4);

end.

Ta có thể coi phép toán tích cực ở đây là: p := p * x / j;

Số lần thực hiện phép toán này là: 0 + 1 + 2 + … + n = n(n - 1)/2 lần.

Vậy độ phức tạp tính toán của thuật toán là O(n2).

ĐỘ 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ẽ phải xét tới trường hợp tốt nhất, trường hợp trung bình và trường  hợp xấu nhất. Khi khó khăn trong việc xác định độ phức tạp tính toán trong trường hợp 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ụ 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.

CHI PHÍ THỰC HIỆN THUẬT TOÁN

Khái niệm độ phức tạp tính toán đặt ra là để đánh giá chi phí thực hiện một giải thuật về mặt thời gian. Nhưng chi phí thực hiện giải thuật còn có rất nhiều yếu tố khác nữa: không gian bộ nhớ phải sử dụng là một ví dụ. Tuy nhiên, trên phương diện phân tích lý thuyết, ta chỉ có thể xét tới vấn đề thời gian bởi việc xác định các chi phí khác nhiều khi rất mơ hồ và phức tạp. Đối với người lập trình thì khác, một thuật toán với độ phức tạp dù rất thấp cũng sẽ là vô dụng nếu như không thể cài đặt được trên máy tính, chính vì vậy khi bắt tay cài đặt một thuật toán, ta phải biết cách tổ chức dữ liệu một cách khoa học, tránh lãng phí bộ nhớ không cần thiết. Có một quy luật tương đối khi tổ chức dữ liệu: Tiết kiệm được bộ nhớ thì thời gian thực hiện thường sẽ chậm hơn và ngược lại. Biết cân đối, dung hoà hai yếu tố đó là một kỹ năng cần thiết của người lập trình.

Bài tập

Bài 1

Chứng minh một cách chặt chẽ: Tại sao với P(n) là đa thức bậc k thì một giải thuật cấp O(P(n)) cũng có thể coi là cấp O(nk)

Bài 2

Xác định độ phức tạp tính toán của những giải thuật sau bằng ký pháp chữ O lớn:

a) Đoạn chương trình tính tổng hai đa thức:

P(x) = amxm + am-1xm-1 + … + a1x + a0 và Q(x) = bnxn + an-1xn-1 + … + b1x + b0

Để được đa thức:

R(x) =  cpxp + cp-1xp-1 + … + c1x + c0

if m < n then p := m else p := n; {p = min(m, n)}

for i := 0 to p do c[i] := a[i] + b[i];

if p < m then

for i := p + 1 to m do c[i] := a[i]

else

for i := p + 1 to n do c[i] := b[i];

while (p > 0) and (c[p] = 0) do p := p - 1;

b) Đoạn chương trình tính tích hai đa thức:

P(x) = amxm + am-1xm-1 + … + a1x + a0 và Q(x) = bnxn + an-1xn-1 + … + b1x + b0

Để được đa thức:

R(x) =  cpxp + cp-1xp-1 + … + c1x + c0

p := m + n;

for i := 0 to p do c[i] := 0; for i := 0 to m do

for j := 0 to n do

c[i + j] := c[i + j] + a[i] * b[j];

« Prev
Next »