Trong phân tích lý thuyết các thuật toán, người ta thường ước tính độ phức tạp của chúng theo nghĩa tiệm cận, tức là ước tính hàm độ phức tạp cho đầu vào lớn tùy ý. Thuật ngữ "phân tích các thuật toán" được đặt ra bởi Donald Knuth.
Phân tích thuật toán là một phần quan trọng của lý thuyết độ phức tạp tính toán, lý thuyết này cung cấp ước tính lý thuyết cho các tài nguyên cần thiết của một thuật toán để giải quyết một vấn đề tính toán cụ thể. Hầu hết các thuật toán được thiết kế để hoạt động với các đầu vào có độ dài tùy ý. Phân tích các thuật toán là việc xác định lượng tài nguyên thời gian và không gian cần thiết để thực thi nó.
Thông thường, hiệu quả hoặc thời gian chạy của một thuật toán được nêu dưới dạng một hàm liên quan đến độ dài đầu vào với số bước, được gọi là độ phức tạp thời gian hoặc dung lượng bộ nhớ, được gọi là độ phức tạp của không gian .
Trong Phần này Chúng tôi sẽ đề cập đến -
- Thuật toán và độ phức tạp
- Phân tích tiệm cận
- Kí hiệu tiệm cận
- Phân tích khấu hao
- Độ phức tạp của không gian
- Thuật toán kiểu đa thức giả và PATS (Sơ đồ xấp xỉ kiểu đa thức giả)