ในบริบทของการเขียนโปรแกรม Algorithm คือชุดคำสั่งที่ชัดเจนเรียงลำดับเพื่อทำงานเฉพาะและได้ผลลัพธ์ที่ต้องการ ที่นี่กล่าวถึงชุดคำสั่งที่กำหนดไว้ หมายความว่าที่ใดผู้ใช้รู้ผลลัพธ์ของคำสั่งเหล่านั้นหาก execute ตามที่คาดไว้
จากความรู้เกี่ยวกับผลลัพธ์ของคำสั่ง มีอัลกอริทึม 2 ประเภทคือ Deterministic และ Non-deterministic Algorithms ความแตกต่างหลักมีดังนี้ −
| Sr. No. | Key | Deterministic Algorithm | Non-deterministic Algorithm |
|---|---|---|---|
| 1 | Definition (นิยาม) | อัลกอริทึมที่ผลลัพธ์ของทุกอัลกอริทึมถูกนิยามอย่างชัดเจน เรียกว่า Deterministic Algorithm กล่าวอีกนัยหนึ่ง อัลกอริทึมที่ทำงานจำนวนขั้นตอนคงที่ และจบเสมอด้วย accept หรือ reject state ด้วยผลลัพธ์เดียวกัน | อัลกอริทึมที่ผลลัพธ์ไม่ถูกนิยามอย่างชัดเจน และอาจสุ่ม เรียกว่า Non-Deterministic Algorithm |
| 2 | Execution (การทำงาน) | ใน Deterministic Algorithms เครื่องเป้าหมาย execute คำสั่งเดียวกันและได้ผลลัพธ์เดียวกัน ไม่ขึ้นกับวิธีหรือกระบวนการที่คำสั่งถูก execute | ใน Non-Deterministic Algorithms เครื่องที่ execute แต่ละ operation ได้รับอนุญาตให้เลือกผลลัพธ์ใดก็ได้จากผลลัพธ์เหล่านี้ ตาม determination condition ที่จะนิยามภายหลัง |
| 3 | Type (ประเภท) | จาก execution และ outcome ใน Deterministic algorithm จัดเป็น reliable algorithms เนื่องจากสำหรับ input เหมือนกัน เครื่องจะให้ output เดียวกันเสมอ | Non deterministic algorithms จัดเป็น non-reliable algorithms เนื่องจาก input เดียวกัน เครื่องให้ output ต่างกันในแต่ละ execution |
| 4 | Execution Time (เวลาทำงาน) | เนื่องจาก outcome รู้จักและสอดคล้องในการ execute ต่างๆ Deterministic algorithm ใช้ polynomial time | เนื่องจาก outcome ไม่รู้จักและไม่สอดคล้อง Non-Deterministic algorithm อาจไม่ execute ใน polynomial time ได้ |
| 5 | Execution path (เส้นทางการทำงาน) | ใน deterministic algorithm เส้นทาง execution เหมือนกันทุก execution | ใน Non-Deterministic algorithm เส้นทาง execution ไม่เหมือนกัน และอาจเลือกเส้นทางสุ่มได้ |
