비결정적 알고리즘

f(n) 개의 단계를 수행하는 결정론적 알고리즘은 언제나 f(n) 개의 단계를 수행하며 언제나 같은 결과를 도출한다. f(n) 개 높이의 단계를 수행하는 비결정론적 알고리즘은 수행할 때마다 다른 과정을 거쳐서, 언제나 같은 결과를 도출하지 않을 수 있다. 비결정론적 알고리즘은 수행도의 높이는 고정되어 있더라도 그 크기는 무한할 수 있기 때문에 영원히 끝나지 않을 수도 있다.

비결정론적 알고리즘(영어: Nondeterministic algorithm)은 결정론적 알고리즘과는 달리, 동일한 입력이 주어지더라도 매번 다른 과정을 거쳐 다른 결과를 도출하는 알고리즘을 의미한다.

참고 문서

• 비결정론적 튜링 기계
• 비결정론적 프로그래밍(:en:Nondeterministic programming)

참고 문헌

• Cormen, Thomas H. (2009). 《Introduction to Algorithms》 3판. MIT Press. ISBN 978-0-262-03384-8. 
• “Nondeterministic algorithm”. National Institute of Standards and Technology. 2013년 7월 7일에 확인함. 
• “Non-deterministic Algorithms”. New York University Computer Science. 2007년 10월 26일에 원본 문서에서 보존된 문서. 2013년 7월 7일에 확인함.