XÁC ĐỊNH ĐỘ PHỨC TẠP THUẬT TOÁN - Lập Trình

Cách tính độ phức tạp của một số giải thuật đơn giản.

QUY TẮC XÁC ĐỊNH ĐỘ PHỨC TẠP

• Độ phức tạp tính toán của giải thuật: O(f(n))

• Việc xác định độ phức tạp tính toán của giải thuật trong thực tế có thể tính bằng một số quy tắc đơn giản sau:

– Quy tắc bỏ hằng số:

T(n) = O(c.f(n)) = O(f(n)) với c là một hằng số dương

– Quy tắc lấy max:

T(n) = O(f(n)+ g(n)) = O(max(f(n), g(n)))

– Quy tắc cộng:

T1(n) = O(f(n)) T2(n) = O(g(n))

T1(n) + T2(n) = O(f(n) + g(n))

– Quy tắc nhân:

Đoạn chương trình có thời gian thực hiện T(n)=O(f(n))

Nếu thực hiện k(n) lần đoạn chương trình với k(n) = O(g(n)) thì độ phức tạp sẽ là O(g(n).f(n))

PHÉP TOÁN TÍCH CỰC (BEST PROXY)

• Trong một thuật toán, ta chú ý đặc biệt đến một phép toán gọi là phép toán tích cực. Đó là phép toán mà số lần thực hiện không ít hơn các phép toán khác

• Ví dụ 1:

s = 0;

for (i=0; i<=n;i++){

p =1;

for (j=1;j<=i;j++)

p=p * x / j;

s = s+p;

}

Phép toán tích cực 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 = n2/2 – n/2

=> Vậy độ phức tạp là O(n2/2 – n/2)

= O(n2/2) sử dụng quy tắc lấy max

= O(n2) sử dụng quy tắc bỏ hằng số

• Ví dụ 2:

s = 1; p = 1;

for (i=1;i<=n;i++) {

p = p * x / i;

s = s + p;

}

Phép toán tích cực là p = p * x / i

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

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

• Ví dụ 3:

s=n*(n-1) /2;

=> Độ phức tạp của thuật toán là O(1), nghĩa là thời gian tính toán không phụ thuộc vào n

• Ví dụ 4:

Thuật toán tính tổng các số từ 1 đến n

s=0;

for (i= 1;i<=n;i++)

s=s+i;

Vòng lặp 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 độ phức tạp là O(n).

=> độ phức tạp là O(n)

• Ví dụ 5:

for (i= 1;i<=n;i++) for (j= 1;j<=n;j++) //Lệnh

=> Dùng quy tắc nhân ta có O(n^2) tương tự như vậy ta sẽ có O(n^3), O(n^4).

• Ví dụ 6:

for (i= 1;i<=n;i++) for (j= 1;j<=m;j++)

//Lệnh => Dùng quy tắc nhân ta có O(n*m)

• Ví dụ 7:

for (i= 1;i<=n;i++) //lệnh1 for (j= 1;j<=m;j++) //lệnh 2 => Dùng quy tắc cộng và quy tắc lấy max, sẽ có

O(max (n,m))

• Ví dụ 8:

for (i= 1;i<=n;i++) {

for (u= 1;u<=m;u++)

for (v= 1;v<=n;v++)

//lệnh

for j:= 1 to x do

for k:= 1 to z do

//lệnh

}

=> O(n*max (n*m,x*z))

• Ví dụ 9:

for (i= 1;i<=n;i++)

for (j= 1;j<=m;j++) {

for (k= 1;k<=x;k++)

//lệnh

for (h= 1;h<=y;h++)

//lệnh

}

=> O(n*m* max (x,y))

• Ví dụ 10:

for (i= 1;i<=n;i++)

for (u= 1;u<= m;u++)

for (v= 1;v<=n;v++)

//lệnh

for (j= 1;j<=x;j++)

for (k= 1;k<=z;k++)

//lệnh

=> O(max (m*n^2,x*z))

• Ví dụ 11: Đoạn chương trình tính tổng 2 đa thức

P(x) = xmxm+am-1xm-1+ …+a1x+a0

Q(x) = bnxn+bn-1xn-1+…+b1x+b0

if (m<n) p = m; else p =n;

for (i=0;i<=p;i++)

c[i]=a[i] + b[i];

if (p<m)

for (i=p+1;i<=m;i++) c[i] = a[i];

else

for (i=p+1;i<=n;i++) c[i] = b[i];

while (p>0 && c[p] = 0) p = p-1;

=> Độ phức tạp: O(max(m,n))

• Ví dụ 12: Đoạn chương trình tính tích hai đa thức

P(x) = xmxm+am-1xm-1+ …+a1x+a0

Q(x) = bnxn+bn-1xn-1+…+b1x+b0

p = m+n;

for (i=0;i<=p;i++) c[i] = 0;

for (i=0;i<=m;i++)

for (j=0;j<=n;j++)

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

=> Độ phức tạp là O(m.n)

Sắp xếp theo chiều tăng của độ phức tạp, các độ phức tạp đặt trên cùng hàng là tương đương

1, 2100

log n

n log n, log (n!)

n2

(log n)log n, nlog(log n)

2n

3n n!