Big O: Cách Tính Độ Phức Tạp Của Thời Gian Và Không Gian

Bạn đang xem: Big o: cách tính độ phức tạp của thời gian và không gian

Xem thêm: Dạy Lớp 1 Theo Chương Trình Tiểu Học Mới, Khó Khăn Khi Triển Khai Chương Trình Giáo Dục Mới

Cách tính độ tinh vi của một vài giải thuật solo giản.

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

• Độ phức tạp thống kê giám sát của giải thuật: O(f(n))

• Việc khẳng định độ phức tạp đo lường và tính toán của lời giải trong thực tế hoàn toàn có thể tính bằng một số quy tắc đơn giản dễ dàng sau:

– Quy tắc quăng quật hằng số:

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

– Quy tắc đem 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 công tác có thời gian thực hiện tại T(n)=O(f(n))

Nếu tiến hành k(n) lần đoạn công tác với k(n) = O(g(n)) thì độ tinh vi 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 để ý đặc biệt mang đến một phép toán hotline 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 những phép toán khác

• lấy ví dụ 1:

s = 0;

for (i=0; i2/2 – n/2

=> Vậy độ tinh vi là O(n2/2 – n/2)

= O(n2/2) áp dụng quy tắc rước max

= O(n2) thực hiện quy tắc vứt hằng số

• lấy ví dụ như 2:

s = 1; p. = 1;

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

• lấy một 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 giám sát không nhờ vào vào n

• ví dụ như 4:

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

s=0;

for (i= 1;i độ phức hợp là O(n)

• ví dụ 5:

for (i= 1;i for (j= 1;j //Lệnh

=> dùng quy tắc nhân ta có O(n^2)tương tự vì thế ta sẽ sở hữu O(n^3), O(n^4).

• ví dụ 6:

for (i= 1;i for (j= 1;j=> sử dụng quy tắc nhân ta có O(n*m)

• lấy ví dụ 7:

for (i= 1;i //lệnh1for (j= 1;j //lệnh 2=> cần sử dụng quy tắc cùng và quy tắc mang max, vẫn có

O(max (n,m))

• lấy ví dụ 8:

for(i=1;i O(n*max (n*m,x*z))

• lấy ví dụ như 9:

for(i=1;i O(n*m* max (x,y))

• lấy ví dụ như 10:

for(i=1;i O(max (m*n^2,x*z))

• lấy một 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 (m0 && c

= 0) p. = p-1;

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

• lấy ví dụ như 12: Đoạn lịch trình tính tích hai nhiều 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 Độ phức tạp là O(m.n)

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