프로그래밍의 맥락에서 알고리즘은 특정 작업을 수행하고 원하는 출력을 달성하기 위해 순서대로 잘 정의된 명령어 세트입니다. 여기에서 정의된 명령어 세트를 말합니다. 이는 사용자가 예상한 방식으로 실행될 경우 해당 명령어의 결과를 어딘가에서 알고 있음을 의미합니다.
명령의 결과에 대한 지식을 기반으로 두 가지 유형의 알고리즘, 즉 결정적 및 비결정적 알고리즘이 있습니다. 다음은 두 알고리즘의 주요 차이점입니다 -
| Sr. 아니요. | 키 | 결정적 알고리즘 | 비결정적 알고리즘 |
|---|---|---|---|
| 1 | 정의 | 모든 알고리즘의 결과가 고유하게 정의되는 알고리즘을 결정론적 알고리즘이라고 합니다. 즉, 결정론적 알고리즘은 고정된 수의 단계를 수행하고 항상 동일한 결과로 승인 또는 거부 상태로 완료되는 알고리즘이라고 말할 수 있습니다. | 반면, 모든 알고리즘의 결과가 고유하게 정의되지 않고 결과가 임의적일 수 있는 알고리즘을 비결정적 알고리즘(Non-Deterministic Algorithm)이라고 합니다. |
| 2 | 실행 | 결정적 알고리즘 실행에서 대상 머신은 동일한 명령어를 실행하고 명령어가 실행되는 방식이나 프로세스에 의존하지 않는 동일한 결과를 생성합니다. | 반면, Non-Deterministic Algorithms의 경우, 각 연산을 수행하는 기계는 나중에 정의할 결정 조건에 따라 이러한 결과 중 하나를 선택할 수 있습니다. |
| 3 | 유형 | 결정론적 알고리즘의 경우 실행 및 결과에 따라 특정 입력 명령에 대해 기계가 항상 동일한 출력을 제공하므로 신뢰할 수 있는 알고리즘으로도 분류됩니다. | 반면에 비결정적 알고리즘은 특정 입력에 대해 신뢰할 수 없는 알고리즘으로 분류되며 기계는 실행에 따라 다른 출력을 제공합니다. |
| 4 | 실행 시간 | 결과가 알려져 있고 다른 실행에서 일관성이 있으므로 결정적 알고리즘은 실행에 다항식 시간이 걸립니다. | 반면에 결과가 알려지지 않고 다른 실행에서 일관성이 없기 때문에 비결정적 알고리즘은 다항식 시간에 실행될 수 없습니다. |
| 5 | 실행 경로 | 결정적 알고리즘에서 알고리즘의 실행 경로는 모든 실행에서 동일합니다. | 반면에 비결정적 알고리즘의 경우 실행 경로는 모든 실행에서 알고리즘에 대해 동일하지 않으며 실행을 위해 임의의 경로를 취할 수 있습니다. |