Thuật toán
Thuật toán là tập hữu hạn các lệnh, nếu tuân theo sẽ hoàn thành một nhiệm vụ cụ thể. Nó không phụ thuộc ngôn ngữ, có thể dùng bất kỳ ngôn ngữ và ký hiệu nào để biểu diễn lệnh.
Tiêu chuẩn của thuật toán
- Đầu vào: Không hoặc nhiều đầu vào được cung cấp từ bên ngoài cho thuật toán.
- Đầu ra: Ít nhất một đầu ra được tạo ra bởi thuật toán.
- Tính xác định: Mỗi lệnh rõ ràng và không mơ hồ.
- Tính hữu hạn: Thuật toán sẽ kết thúc sau số bước hữu hạn đối với mọi trường hợp.
- Tính hiệu quả: Mỗi lệnh phải cơ bản, mục đích của các lệnh phải rõ ràng.
Phân tích thuật toán
Phân tích thuật toán là phần quan trọng của lý thuyết độ phức tạp tính toán. Lý thuyết độ phức tạp cung cấp ước lượng lý thuyết về tài nguyên cần thiết cho thuật toán để giải quyết bài toán tính toán. Phân tích thuật toán là quá trình phân tích khả năng giải quyết vấn đề của thuật toán về mặt thời gian và kích thước yêu cầu (kích thước bộ nhớ lưu trữ khi cài đặt). Tuy nhiên, mối quan tâm chính là thời gian yêu cầu hoặc hiệu năng.
Độ phức tạp của thuật toán
Độ phức tạp của thuật toán tính lượng thời gian và không gian cần thiết cho đầu vào kích thước (n). Độ phức tạp chia thành hai loại: độ phức tạp thời gian và độ phức tạp không gian.
Độ phức tạp thời gian của thuật toán
Độ phức tạp thời gian được định nghĩa là quá trình xác định công thức tổng thời gian cần thiết cho việc thực thi thuật toán. Tính toán này hoàn toàn độc lập với cài đặt và ngôn ngữ lập trình.
Độ phức tạp không gian của thuật toán
Độ phức tạp không gian được định nghĩa là quá trình xác định công thức dự đoán lượng không gian bộ nhớ cần thiết để thực thi thành công thuật toán. Không gian bộ nhớ thường được xem là bộ nhớ chính.