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 = n²/2 – n/2

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

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

= O(n²)           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) = x_mx^m+a_m-1x^m-1+ …+a₁x+a₀

Q(x) = b_nxⁿ+b_n-1x^n-1+…+b₁x+b₀

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) = x_mx^m+a_m-1x^m-1+ …+a₁x+a₀

Q(x) = b_nxⁿ+b_n-1x^n-1+…+b₁x+b₀

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, 2¹⁰⁰

            log n

            n log n, log (n!)

            n²

            (log n)^{log n}, n^{log(log n)}

            2ⁿ

3ⁿ
n!