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!