Độ phức tạp thuật toán

Thời gian mà máy tính khi thực hiện một thuật toán không chỉ phụ thuộc vào bản thân thuật toán đó, ngoài ra còn tùy thuộc từng máy tính. Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp thuật toán là một hàm phụ thuộc đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng.
Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc O-lớn và bậc Θ (bậc Theta).
Bậc O-lớn.
Gọi formula_1 là độ lớn đầu vào. Tùy thuộc từng bài toán mà formula_1 có thể nhận những giá trị khác nhau. Chẳng hạn, bài toán tính giai thừa thì formula_1 chính là số cần tính giai thừa. Nhiều bài toán số trị, chẳng hạn tính sai phân thì formula_1 là số chữ số có nghĩa cần đạt được. Trong các phép tính đối với ma trận thì formula_1 là số hàng hoặc cột của ma trận.
Độ phức tạp của bài toán phụ thuộc vào formula_1. Ở đây ta không chỉ đặc trưng độ phức tạp bởi số lượng phép tính, mà dùng một đại lượng tổng quát là "tài nguyên cần dùng" formula_7. Đó có thể là số lượng phép tính (có thể tính cả số lần truy nhập bộ nhớ, hoặc ghi vào bộ nhớ); nhưng cũng có thể là thời gian thực hiện chương trình ("độ phức tạp về thời gian") hoặc dung lượng bộ nhớ cần phải cấp để chạy chương trình ("độ phức tạp về không gian").
Xét quan hệ giữa tài nguyên và độ lớn đầu vào, nếu như tìm được hằng số formula_8, formula_9 không phụ thuộc vào formula_1, sao cho với formula_1 đủ lớn, các hàm formula_12 đều dương và
thì ta nói thuật toán có độ phức tạp cỡ formula_14.
Diễn giải.
Độ phức tạp không phải là độ đo chính xác lượng tài nguyên máy cần dùng, mà đặc trưng cho động thái của hệ thống khi kích thước đầu vào tăng lên. Chẳng hạn với thuật toán có độ phức tạp tuyến tính formula_15 (xem phần dưới), nếu kích thước đầu vào tăng gấp đôi thì có thể ước tính rằng tài nguyên cần dùng cũng tăng khoảng gấp đôi. Nhưng với thuật toán có độ phức tạp bình phương formula_16 thì tài nguyên sẽ tăng gấp bốn. Mặt khác, với thuật toán có độ phức tạp hàm mũ formula_17 thì chỉ cần công thêm 2 đơn vị vào độ lớn đầu vào cũng đã làm tài nguyên tăng gấp 4 lần (tức là theo cấp số nhân) rồi.
Các độ phức tạp thường gặp đối với các thuật toán thông thường gồm có:
Lưu ý.
Định nghĩa trên mang tính "an toàn" theo nghĩa nó chỉ xét sự tiêu tốn tài nguyên không vượt quá một ngưỡng formula_25 nào đó, chứ không nhất thiết đúng bằng formula_25 (chú ý dấu bất đẳng thức). Theo đó, một thuật toán có độ phức tạp cỡ formula_1 thì đồng thời sẽ có độ phức tạp cỡ formula_28; với hàm ý rằng thuật toán này không bao giờ có động thái phức tạp hóa vượt qua ngưỡng đa thức bậc hai.
Bậc Ω và Θ.
Tương tự như với bậc O-lớn, nếu như tìm được các hằng số formula_29 đều dương và không phụ thuộc vào formula_1, sao cho với formula_1 đủ lớn, các hàm formula_32 và formula_33 đều dương và
thì ta nói thuật toán có độ phức tạp cỡ lớn hơn formula_36, và đúng bằng cỡ formula_37.
Như vậy nếu xét một cách chặt chẽ, ký hiệu Θ mới biểu thị độ phức tạp của thuật toán một cách chặt chẽ. Tuy nhiên qua một thời gian dài ký hiệu formula_15 cũng đã được dùng phổ biến, chẳng hạn .
 khong tin dau