XÁC ĐỊNH ĐỘ PHỨC TẠP THUẬT TOÁN – Lập trình – Khoa Công nghệ thông tin – Đại học Duy Tân

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!

Related Posts

Lưu ngay Top cách xóa lịch sử trên máy tính vĩnh viễn hàng đầu 2023

Dưới đây là những chia sẻ chi tiết của chúng tôi về cách xóa lịch sử trên máy tính vĩnh viễn được cập nhật mới nhất? Hãy tham khảo ngay những thông tin mà chúng tôi chia sẻ dưới đây, nếu thấy hay hãy chia sẻ bài viết này nhé!

Mẹo hay Top pin 4000mah sạc bao lâu thì đầy hot nhất hiện nay 2023

Trong bài viết này, chúng tôi chia sẻ một số thông tin về pin 4000mah sạc bao lâu thì đầy được cập nhật mới nhất? Hãy tham khảo ngay những thông tin mà chúng tôi chia sẻ dưới đây, nếu thấy hay hãy chia sẻ bài viết này nhé!

Mẹo hay Top cách bật cảm biến con quay hàng đầu 2023

Để hiểu hơn về cách bật cảm biến con quay được cập nhật mới nhất? Hãy tham khảo ngay những thông tin mà chúng tôi chia sẻ dưới đây, nếu thấy hay hãy chia sẻ bài viết này nhé!

Mẹo hay Top các trường đại học ở daegu hàng đầu 2023

Hãy cùng Nhà Xinh tìm hiểu rõ hơn về các trường đại học ở daegu được cập nhật mới nhất? Hãy tham khảo ngay những thông tin mà chúng tôi chia sẻ dưới đây, nếu thấy hay hãy chia sẻ bài viết này nhé!

Tổng hợp Top cách chăm sóc gà choi con mới nở [Hot Nhất 2023]

Dưới đây là những chia sẻ chi tiết của chúng tôi về cách chăm sóc gà choi con mới nở được viết khách quan và đầy đủ nhất, bạn hãy tham khảo ngay thông tin dưới đây của chúng tôi, nếu thấy hay hãy chia sẻ bài viết này nhé!

Tổng hợp Top cách làm video có chữ chạy trên điện thoại hàng đầu 2023

Dưới đây là những chia sẻ chi tiết của chúng tôi về cách làm video có chữ chạy trên điện thoại được cập nhật mới nhất? Hãy tham khảo ngay những thông tin mà chúng tôi chia sẻ dưới đây, nếu thấy hay hãy chia sẻ bài viết này nhé!