Độ Phức Tạp Của Thuật Toán Và Lựa Chọn Cách Tính

Hiểu và đo lường độ phức tạp của thuật toán không chỉ giúp chúng ta đánh giá được hiệu suất và hiệu quả của thuật toán, mà còn giúp chúng ta thiết kế và tối ưu hóa các thuật toán để đạt được hiệu quả tốt nhất. Trong bài viết này, chúng ta sẽ khám phá sâu hơn về độ phức tạp của thuật toán, từ khái niệm cơ bản đến cách tính toán và đo lường độ phức tạp.

Bắt đầu từ những nguyên tắc cơ bản, chúng ta sẽ tiếp cận với một lĩnh vực quan trọng trong khoa học máy tính và khám phá cách xác định và áp dụng độ phức tạp trong thiết kế thuật toán hiệu quả. Hãy cùng THVM theo dõi ngay thôi!.

Độ phức tạp của thuật toán là gì?

Độ phức tạp của thuật toán (biểu diễn bằng Notation Big-O), là một biểu thức mô tả hành vi của thuật toán (ví dụ, về mặt thời gian tính toán hoặc lượng bộ nhớ cần sử dụng) khi kích thước dữ liệu thay đổi.

Nói cách khác, Big O mô tả mối quan hệ giữa số lượng phần tử đầu vào và số lượng phép toán – thời gian chạy, hoặc số lượng bộ nhớ mà thuật toán cần sử dụng.

Để hiểu rõ hơn, bạn có thể theo dõi vào hình dưới đây:

Với các thuật toán có độ phức tạp O(n), khi có 10 phần tử dữ liệu đầu vào, chương trình sẽ chạy 10 lần. Khi số lượng dữ liệu đầu vào tăng gấp đôi, số lượng câu lệnh cũng tăng gấp đôi.

Giới thiệu về Viện Nghiên cứu Hợp tác Phát triển Giáo Dục (IED)Xem thêm

Nếu độ phức tạp là O(n²), khi số lượng dữ liệu đầu vào tăng gấp đôi, số lượng câu lệnh sẽ tăng gấp 4.

Tóm lại, thuật toán có độ phức tạp càng cao, khi số lượng dữ liệu càng nhiều, thời gian chạy càng lâu.

Ví dụ về độ phức tạp của thuật toán

• Một mảng có n phần tử. Hãy tìm phần tử lớn nhất trong mảng. Bài này tất nhiên không có cách nào khác, bạn sẽ duyệt toàn bộ phần tử trong mảng (duyệt qua mảng n lần) để tìm ra phần tử lớn nhất. Độ phức tạp thuật toán ở đây có thể hiểu là O(n) (chạy qua n phần tử để tìm kiếm).
• Cho một mảng có n phần tử đã sắp xếp. Hãy tìm xem có phần tử x hay không? Bài này nếu các bạn duyệt từ 1 tới n để tìm xem có x hay không, độ phức tạp vẫn là O(n). Tuy nhiên nếu để ý, do mảng này là mảng đã sắp xếp, nên bạn có thể áp dụng thuật toán tìm kiếm nhị phân. Tức là bạn chặt dãy ra làm 2, xem X lớn hay nhỏ hơn phần tử ở giữa, nếu nhỏ hơn thì tìm kiếm ở đoạn dưới, nếu lớn hơn thì tìm kiếm ở đoạn trên. Cứ như vậy bạn chặt dãy ra làm 2 liên tục, thì số phép tìm kiếm sẽ là log2 của n, sẽ nhanh hơn nhiều lần so với giải thuật tìm kiếm tuần tự bên trên.
• Một mảng có n phần tử. Hãy sắp xếp mảng theo thứ tự tăng dần. Bài này quá quen rồi. Bạn thường dùng 2 vòng lặp từ i đến n và từ j đến n để đổi chỗ. Lúc này độ phức tạp thuật toán là O(n^2). Tuy nhiên với một số giải thuật sắp xếp như quicksort, độ phức tạp chỉ là O(nlog(n)). Bạn thử thay n=10, thì giải thuật bên trên có thể hiểu sẽ chạy xấp xỉ là 1010=100 phép tính, nhưng giải thuật Quicksort thì chỉ dùng khoảng 10 phép tính. Với n rất nhỏ, 100 hay 1000 thì chương trình đều chạy có thời gian xấp xỉ bằng nhau. Thật ra kết quả là có chênh, nhưng quá nhỏ nên các bạn không thấy. Nhưng với n cực lớn, ví dụ 100000 phần tử, thì thuật toán có độ phức tạp O(n^2) với O(nlogn) là cực kì khác biệt.

Tốc độ của máy tính của chúng ta khác nhau. Có thể hiểu rằng, nếu cùng thực hiện 100000 phép tính, máy của ông A có thể chạy nhanh hơn máy ông B. Do đó, độ phức tạp của thuật toán có thể cho thấy rõ ràng thuật toán nào nhanh hơn hay chậm hơn, so với việc đo thời gian chạy trên các máy khác nhau. Nhiều người đã bình luận về việc tại sao thời gian chạy trên máy ở nhà lại không lâu như trên máy chủ. Cũng có cùng một lý do như vậy.

Cách tính độ phức tạp của thuật toá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:

Xếp Loại Chứng Chỉ Tin Học Cơ Bản Hiện Nay Và Tầm Quan TrọngXem thêm

– 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++)

=> 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(nmax (nm,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(nm 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 (mn^2,xz))

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

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

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

if (p

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!

Chọn cách tính phù hợp để giải thuật

Như đã được giải thích ở trên, độ phức tạp của một thuật toán có thể hiểu là số lượng phép toán mà một hàm thực hiện dựa trên kích thước tối đa của dữ liệu. Độ phức tạp của một thuật toán (trên cùng một máy) có thể hiểu là nó tăng lên tỉ lệ thuận (một cách tương đối) với thời gian chạy. Khi đánh giá được độ phức tạp của thuật toán thì bạn dễ dàng chọn cho mình cách tình phù hợp nhất để giải thuật.

Cùng theo dõi ví dụ sau đây:

– Bài toán tính tổng các số nguyên từ 1 đến n:

Nếu ai đó dùng công thức, chỉ cần một dòng là xong: n*(n+1)/2. Giải thuật này có độ phức tạp là O(1) (một phép toán). Nhưng nếu các bạn sử dụng vòng lặp từ 1 đến n để tính tổng, độ phức tạp sẽ là O(n). Với n = 1 tỷ, điều này tương đương với việc bạn thực hiện 1 tỷ lần phép toán cộng. Bạn hiểu sự chênh lệch lớn về thời gian chạy chứ?

– Bài toán kiểm tra số nguyên tố:

Nhiều bạn lại chọn giải thuật phức tạp hơn. Các bạn chạy để kiểm tra từ 1 đến n, độ phức tạp là O(n). Nhưng nếu các bạn chỉ chạy từ 1 đến căn bậc hai của n (sqrt(n)), số lượng phép toán đã giảm rất nhiều. Nếu bạn còn tăng bước nhảy lên 2 (kiểm tra có chia hết cho 2,3,5,7,9,11,… thay vì 2,3,4,5,6,…), số lượng phép toán sẽ giảm thêm nữa. Vì vậy, ngay từ bài toán kiểm tra số nguyên tố, việc sử dụng vòng lặp để kiểm tra đã giúp bạn tối ưu rất nhiều. Bạn có thể thử bài này với số n rất lớn và thực hiện nhiều lần để đo sự chênh lệch về thời gian.

– Bài toán tính tổng các số nguyên tố nhỏ hơn hoặc bằng n:

Cũng tương tự. Độ phức tạp của việc kiểm tra số nguyên tố giả sử là O(n). Nếu bạn lặp lại việc kiểm tra cho mỗi số từ 1 đến n theo cách thông thường, độ phức tạp của giải thuật này sẽ là O(n^2). Với n = 1 triệu, hầu hết sẽ không thể chạy được do số lượng phép toán quá nhiều. Tuy nhiên, nếu bạn sử dụng sàng nguyên tố (ý tưởng là loại bỏ các số hợp số), độ phức tạp của thuật toán gần như là O(nlogn).

Tổng kết lại

Hiểu rõ về khái niệm độ phức tạp của thuật toán và cách tính toán độ phức tạp của giải thuật, bạn có thể tối ưu hóa thuật toán để đạt hiệu suất chạy tốt hơn. Ví dụ, bạn có thể làm cho ứng dụng của bạn chạy nhanh hơn và có thời gian phản hồi ngắn hơn. Vì vậy, khi đối mặt với mỗi bài toán cụ thể hoặc yêu cầu, hãy xem xét kích thước của tập dữ liệu và chọn giải thuật phù hợp.

Hi vọng qua bài viết này, các bạn đã đánh giá được độ phức tạp của thuật toán và có hướng xử lý chúng một cách nhanh gọn nhẹ nhất. Chúc các bạn thành công! 😀

Cổng Thông Tin Thương Hiệu Vùng Miền

Cung cấp thông tin chính xác, tích cực cho người dân về nông nghiệp, nông sản Việt Nam. Cập nhật tin tức mới nhất về tình hình sản xuất nông nghiệp; hướng dẫn kỹ thuật chăn nuôi, trồng trọt, chia sẻ, phổ biến mô hình làm giàu hiệu quả và bền vững. Chia sẻ các kiến thức xã hội trong nhiều lĩnh vực khác như Giáo dục, du lịch,…