确定性算法与非确定性算法的区别

在编程领域，算法是一组定义明确的、按顺序执行特定任务并实现预期输出的指令。这里我们说“一组定义明确的指令”，这意味着用户在某种程度上知道如果这些指令以预期的方式执行，其结果是什么。

根据对指令结果的了解，算法分为两种类型：确定性算法和非确定性算法。

阅读本文，了解更多关于确定性和非确定性算法的信息，以及它们之间有何不同。

什么是确定性算法？

确定性算法是一种算法，其中每个算法的结果都是唯一定义的。因此，确定性算法执行固定数量的步骤，并且总是以相同的结果完成接受或拒绝状态。目标机器执行相同的指令并给出相同的结果，这并不依赖于指令执行的方式或过程。

确定性算法可以在多项式时间内解决问题。确定性算法总是只有一个结果，即给定的输入总是产生相同的结果。数学函数是确定性算法的一个常见示例。

非确定性算法是一种算法，其中每个算法的输出不是唯一定义的，因此结果可能是随机的。因此，非确定性算法有多个结果。

非确定性算法采用多条执行路径，因此很难确定机器的下一个状态。与确定性算法不同，非确定性算法无法在多项式时间内解决问题。随机函数是非确定性算法的示例。

以下是确定性算法和非确定性算法的主要区别：

关键	确定性算法	非确定性算法
定义	每个算法的结果都是唯一定义的算法称为确定性算法。换句话说，我们可以说确定性算法是执行固定数量步骤并始终以相同的结果完成接受或拒绝状态的算法。	每个算法的结果不是唯一定义的，结果可能是随机的算法称为非确定性算法。
执行	在确定性算法执行中，目标机器执行相同的指令并产生相同的结果，这并不取决于指令执行的方式或过程。	对于非确定性算法，允许执行每个操作的机器选择这些结果中的任何一个，但要遵守稍后定义的确定条件。
类型	根据确定性算法的执行和结果，它们也被分类为可靠算法，因为对于特定的输入指令，机器将始终给出相同的输出。	非确定性算法被分类为不可靠算法，因为对于特定的输入，机器在不同的执行中会给出不同的输出。
执行时间	由于结果已知且在不同的执行中一致，因此确定性算法需要多项式时间来执行。	由于结果未知且在不同的执行中不一致，因此非确定性算法无法在多项式时间内执行。
执行路径	在确定性算法中，算法的执行路径在每次执行中都是相同的。	对于非确定性算法，算法的执行路径在每次执行中并不相同，并且可能采用任何随机路径来执行。

这两种算法之间最显著的区别在于，确定性算法每次执行的执行路径相同，而非确定性算法在不同的执行中可以采用任何随机的执行路径。

Kiran Kumar Panigrahi

更新于：2023年2月21日

20000+ 次浏览

完成课程获得认证