비결정적 알고리즘

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

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

참고 문서

• 비결정론적 튜링 기계
• 비결정론적 프로그래밍(: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일에 확인함.