Mức độ phức tạp của thuật toán

Thời gian thực hiện một thuật toán không chỉ phụ thuộc vào chính thuật toán mà còn vào cấu hình máy tính. Để đánh giá hiệu quả của thuật toán, người ta thường xem xét số phép toán cần thực hiện. Số phép toán thường liên quan đến kích thước bài toán, tức là độ lớn của dữ liệu đầu vào. Do đó, độ phức tạp thuật toán được biểu diễn dưới dạng hàm của đầu vào. Trong thực tế, chúng ta chỉ cần một ước lượng gần đúng của hàm này mà không cần chính xác tuyệt đối.

Để ước lượng độ phức tạp của một thuật toán, người ta thường sử dụng các khái niệm bậc O-lớn và bậc Θ (bậc Theta).

Bậc O-lớn

Ký hiệu k là kích thước đầu vào. Tùy thuộc vào từng bài toán, $n$ có thể mang các giá trị khác nhau. Ví dụ, trong bài toán tính giai thừa, $n$ chính là số giai thừa cần tính. Đối với bài toán số học như tính sai phân, $n$ là số chữ số cần chính xác. Trong các phép toán ma trận, $n$ là số hàng hoặc số cột của ma trận.

Mức độ phức tạp của bài toán phụ thuộc vào $n$. Để đo lường độ phức tạp, chúng ta không chỉ dựa vào số phép tính mà còn vào đại lượng tổng quát là tài nguyên cần sử dụng $R$

( n ) {\displaystyle R(n)} . Tài nguyên này có thể là số phép toán, thời gian thực hiện (độ phức tạp về thời gian) hoặc dung lượng bộ nhớ cần thiết (độ phức tạp về không gian).

Để phân tích mối quan hệ giữa tài nguyên và kích thước đầu vào, nếu chúng ta tìm được một hằng số $C>0$, trong đó $C$ không phụ thuộc vào $n$, và với $n$ đủ lớn, thì các hàm $R\left(n\right),g\left(n\right)$ đều dương và

$R\left(n\right)\le <!--\; \le \; -->C.g\left(n\right)$

thì chúng ta nói thuật toán có độ phức tạp thuộc dạng $O\left(g\right(n\left)\right)$.

Giải thích

Độ phức tạp của thuật toán không chỉ đo lường tài nguyên máy mà còn phản ánh cách hệ thống hoạt động khi kích thước dữ liệu thay đổi. Ví dụ, thuật toán có độ phức tạp tuyến tính O(n) yêu cầu tài nguyên tăng gấp đôi khi kích thước đầu vào gấp đôi. Ngược lại, thuật toán có độ phức tạp bình phương O(n²) làm tài nguyên tăng gấp bốn lần khi đầu vào tăng gấp đôi, và với độ phức tạp hàm mũ O(2^n), chỉ cần tăng thêm 2 đơn vị đầu vào cũng làm tài nguyên tăng gấp 4 lần.

Các loại độ phức tạp thường gặp trong thuật toán bao gồm:

• Độ phức tạp hằng số, O(1), là số phép tính/thời gian chạy/dung lượng bộ nhớ không thay đổi theo kích thước đầu vào, như các thao tác hệ thống đơn giản.
• Độ phức tạp tuyến tính, O(n), khi số phép tính/dung lượng bộ nhớ tỉ lệ thuận với kích thước đầu vào, ví dụ như tính tổng các phần tử trong mảng một chiều.
• Độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao, dùng trong các phép toán phức tạp như tính định thức ma trận.
• Độ phức tạp logarit, O(log n), thấp hơn so với độ phức tạp tuyến tính, như trong thuật toán Euclid để tìm ước số chung lớn nhất.
• Độ phức tạp hàm mũ, O(2^n), là khó thực hiện vì tài nguyên tăng rất nhanh khi kích thước đầu vào tăng.

Lưu ý

Định nghĩa trên chỉ xét đến tài nguyên tiêu tốn không vượt quá một ngưỡng nào đó mà không nhất thiết bằng chính ngưỡng đó. Ví dụ, thuật toán có độ phức tạp O(n) cũng có thể có độ phức tạp O(n²), cho thấy thuật toán này không vượt quá ngưỡng đa thức bậc hai.

Bậc Ω và Θ

Tương tự như bậc O-lớn, nếu có các hằng số C, k1, k2 dương và không phụ thuộc vào n, sao cho với n đủ lớn, các hàm R(n), f(n) và h(n) đều dương và

R(n) ≥ C ⋅ f(n) và k1 ⋅ h(n) ≤ R(n) ≤ k2 ⋅ h(n)

thuật toán có độ phức tạp lớn hơn Ω(f(n)) và chính xác bằng Θ(h(n))

Ký hiệu Θ là chính xác nhất để biểu thị độ phức tạp của thuật toán, mặc dù ký hiệu O(n) cũng được sử dụng phổ biến trong thời gian dài.

• Các lý thuyết về độ phức tạp trong tính toán

• Abelson, Sussman 1993. Cấu trúc và diễn giải các chương trình máy tính. MIT Press, Phiên bản 2.