Trong lập trình, Algorithm là tập hợp hướng dẫn xác định tuần tự để thực hiện nhiệm vụ và đạt output mong muốn. Dựa trên kiến thức về kết quả hướng dẫn, có 2 loại: Deterministic và Non-deterministic.
Các khác biệt chính:
| STT | Key | Deterministic Algorithm | Non-deterministic Algorithm |
|---|---|---|---|
| 1 | Định nghĩa | Kết quả mỗi thuật toán được xác định duy nhất. Thực hiện số bước cố định, luôn kết thúc ở trạng thái accept/reject với cùng kết quả. | Kết quả không xác định duy nhất, có thể ngẫu nhiên. |
| 2 | Thực thi | Máy mục tiêu thực thi cùng lệnh, ra cùng kết quả, không phụ thuộc cách thực thi. | Máy thực thi mỗi phép toán được chọn một trong các kết quả, tuân theo điều kiện xác định sau. |
| 3 | Loại | Reliable algorithms: cùng input → luôn cùng output. | Non-reliable algorithms: cùng input → output khác nhau trên các lần chạy. |
| 4 | Thời gian thực thi | Kết quả nhất quán → chạy trong polynomial time. | Kết quả không nhất quán → không thể chạy trong polynomial time. |
| 5 | Đường dẫn thực thi | Đường dẫn thực thi giống nhau mọi lần. | Đường dẫn thực thi không giống nhau, có thể ngẫu nhiên. |