프로그래밍에서 알고리즘(Algorithm)이란 특정 작업을 수행하고 원하는 출력을 얻기 위해 순서대로 배열된, 잘 정의된 명령어들의 집합을 의미합니다. '정의된 명령어들의 집합'이라고 표현하는 이유는, 사용자가 해당 명령어들이 예상대로 실행되었을 때 어떤 결과가 나올지 미리 알고 있기 때문입니다.
명령어 실행 결과에 대한 지식을 기준으로 알고리즘은 크게 두 가지 유형으로 나눌 수 있습니다. 바로 결정론적(Deterministic) 알고리즘과 비결정론적(Non-deterministic) 알고리즘입니다. 아래에서 두 알고리즘의 주요 차이점을 항목별로 자세히 살펴보겠습니다.
1. 정의 (Definition)
결정론적 알고리즘: 모든 연산의 결과가 고유하게(uniquely) 정의된 알고리즘을 말합니다. 즉, 고정된 개수의 단계를 수행하며, 항상 동일한 결과와 함께 '수락' 또는 '거부' 상태로 종료되는 알고리즘입니다.
비결정론적 알고리즘: 반면 각 연산의 결과가 고유하게 정의되지 않아 결과가 무작위(random)로 달라질 수 있는 알고리즘을 의미합니다.
2. 실행 방식 (Execution)
결정론적 알고리즘: 실행 과정에서 대상 기계가 동일한 명령어를 수행하므로, 명령어가 어떤 방식이나 절차로 처리되었는지와 관계없이 항상 같은 결과를 얻습니다.
비결정론적 알고리즘: 각 연산을 수행하는 기계가 나중에 정의될 판별 조건(determination condition)에 따라 여러 가능한 결과 중 임의로 하나를 선택할 수 있습니다.
3. 신뢰성 분류 (Type)
결정론적 알고리즘: 특정 입력에 대해 항상 동일한 출력을 보장하기 때문에 '신뢰할 수 있는(reliable) 알고리즘'으로 분류됩니다.
비결정론적 알고리즘: 동일한 입력이라도 실행할 때마다 서로 다른 출력이 나올 수 있기 때문에 '신뢰할 수 없는(non-reliable) 알고리즘'으로 분류됩니다.
4. 실행 시간 (Execution Time)
결정론적 알고리즘: 결과가 사전에 예측 가능하고 실행마다 일관성이 유지되므로, 다항 시간(polynomial time) 내에 실행을 마칠 수 있습니다.
비결정론적 알고리즘: 결과가 사전에 알려져 있지 않고 실행마다 일관성이 없기 때문에, 다항 시간 내에 실행이 완료된다는 보장이 없습니다.
5. 실행 경로 (Execution Path)
결정론적 알고리즘: 실행할 때마다 알고리즘이 따르는 실행 경로가 항상 동일합니다.
비결정론적 알고리즘: 실행 경로가 매번 같지 않으며, 실행 시점에 무작위적인 경로를 선택하여 진행할 수 있습니다.
정리
요약하자면, 결정론적 알고리즘은 입력이 주어지면 항상 같은 절차와 같은 결과를 보장하는 예측 가능하고 신뢰성 높은 방식이며, 대표적으로 정렬 알고리즘이나 탐색 알고리즘이 여기에 속합니다. 반면 비결정론적 알고리즘은 실행마다 결과나 경로가 달라질 수 있는 방식으로, 최적화 문제의 근사 해법이나 확률적 접근이 필요한 상황에서 활용됩니다. 문제의 성격과 요구되는 신뢰성 수준에 따라 적절한 알고리즘 유형을 선택하는 것이 중요합니다.