Độ phức tạp tính toán

Trong khoa học máy tính, độ phức tạp tính toán hoặc đơn giản là độ phức tạp của thuật toán là lượng tài nguyên cần thiết để chạy nó. Tập trung đặc biệt được đưa ra cho các yêu cầu thời gian và bộ nhớ.

Vì lượng tài nguyên cần thiết để chạy thuật toán thường thay đổi theo kích thước của đầu vào, độ phức tạp thường được biểu thị dưới dạng hàm n → f(n), trong đó n là kích thước của đầu vào và f(n) là độ phức tạp trong trường hợp xấu nhất (mức tối đa của lượng tài nguyên cần thiết cho tất cả các đầu vào có kích thước n) hoặc độ phức tạp của trường hợp trung bình (trung bình của lượng tài nguyên trên tất cả các đầu vào có kích thước n). Độ phức tạp thời gian thường được biểu thị bằng số lượng các thao tác cơ bản cần thiết trên một đầu vào có kích thước n, trong đó các hoạt động cơ bản được giả định là mất một lượng thời gian không đổi trên một máy tính nhất định và chỉ thay đổi bởi một yếu tố không đổi khi chạy trên một máy tính khác. Độ phức tạp không gian thường được biểu thị bằng lượng bộ nhớ theo yêu cầu của thuật toán trên đầu vào có kích thước n.

Nghiên cứu về độ phức tạp của các thuật toán được đưa ra rõ ràng được gọi là phân tích thuật toán, trong khi nghiên cứu về độ phức tạp của các vấn đề được gọi là lý thuyết độ phức tạp tính toán. Rõ ràng, cả hai lĩnh vực đều có liên quan chặt chẽ với nhau, vì độ phức tạp của thuật toán luôn bị giới hạn trên về độ phức tạp của vấn đề được giải quyết bằng thuật toán này.

Tham khảo