Thuật toán
Thuật toán là một tập hợp hữu hạn các hướng dẫn, nếu được tuân theo, sẽ hoàn thành một nhiệm vụ cụ thể. Nó không dành riêng cho ngôn ngữ, chúng tôi có thể sử dụng bất kỳ ngôn ngữ và ký hiệu nào để thể hiện hướng dẫn.
Tiêu chí của một thuật toán
- Đầu vào: Không hoặc nhiều đầu vào được cung cấp bên ngoài cho thuật toán.
- Đầu ra: Ít nhất một đầu ra được tạo ra bởi một thuật toán.
- Tính xác định: Mỗi hướng dẫn đều rõ ràng và không rõ ràng.
- Tính hữu hạn: Trong một thuật toán, nó sẽ kết thúc sau một số bước hữu hạn cho tất cả các trường hợp khác nhau.
- Hiệu quả: Mỗi hướng dẫn phải rất cơ bản, vì vậy mục đích của những hướng dẫn đó phải rất rõ ràng đối với chúng tôi.
Phân tích các thuật toán
Phân tích thuật toán là một phần quan trọng của tính phức tạp. Lý thuyết độ phức tạp cung cấp các ướ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 bất kỳ tác vụ tính toán nào. 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ề thời gian và kích thước cần thiết (dung lượng bộ nhớ để lưu trữ trong khi thực hiện). Tuy nhiên, mối quan tâm chính của việc phân tích thuật toán là thời gian hoặc hiệu suất cần thiết.
Độ phức tạp của một thuật toán
Độ phức tạp của một thuật toán tính lượng thời gian và không gian mà một thuật toán yêu cầu cho một đầu vào có kích thước (n). Độ phức tạp của một thuật toán có thể được chia thành hai loại. Độ phức tạp về thời gian và độ phức tạp của không gian .
Độ phức tạp về thời gian của một 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 cho tổng thời gian cần thiết để thực hiện thuật toán đó. Tính toán này hoàn toàn độc lập với ngôn ngữ lập trình và triển khai.
Độ phức tạp không gian của một 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 về lượng không gian bộ nhớ cần thiết để thực hiện thành công thuật toán. Không gian bộ nhớ thường được coi là bộ nhớ chính.