什么是确定性算法(a deterministic algorithm)？

确定性算法是一种算法，给定一个特定的输入将始终产生相同的输出，而底层机器始终通过相同的状态序列。换句话说，对于相同的输入，确定性算法总是得到相同的结果。

确定性算法是迄今为止研究最多、最熟悉的算法，也是最实用的算法之一，因为它们可以在实际机器上高效运行。形式上，确定性算法计算数学函数；函数对其域中的任何输入都有唯一的值，而算法是一个将此特定值作为输出的过程。

确定性算法可以用状态机来定义：状态描述机器在特定时刻所做的事情。状态机以离散的方式从一个状态传递到另一个状态。在输入之后，机器处于初始状态或启动状态。如果机器是确定性的，这意味着从这一点开始，其当前状态决定其下一个状态；它通过一组状态的过程是预先确定的。请注意，机器可能是确定性的，但仍然不会停止或完成，因此无法交付结果。

确定性抽象机器的例子包括确定性图灵机和确定性有限自动机。

关于确定性算法你需要知道什么

• 确定性算法是一种算法，给定一个特定的输入将始终产生相同的输出，而底层机器始终通过相同的状态序列。
• 在确定性算法中，算法的执行路径在每次执行中都是相同的。
• 根据确定性算法的执行和结果，它们也被归类为可靠算法，因为对于机器将始终提供相同输出的特定输入指令。
• 在确定性算法执行中，目标机器执行相同的指令并产生相同的结果，这与指令执行的方式或过程无关。
• 由于结果是已知的，并且在不同的执行上是一致的，所以确定性算法的执行需要多项式时间。

什么是一种非确定性算法(a non-deterministic algorithm)？

非确定性算法是一种算法，即使对于相同的输入，在不同的运行中也可能表现出不同的行为。换句话说，它是一种算法，其中每个算法的结果不是唯一定义的，并且结果可能是随机的。

在不确定多项式时间内解决问题的算法可以在多项式时间或指数时间内运行，这取决于它在执行过程中所做的选择。当使用确定性算法获得精确解的成本太高时，通常使用非确定性算法来寻找近似解。

非确定性算法不同于更熟悉的确定性算法，它能够使用不同的路径得出结果。如果确定性算法表示从输入到结果的单一路径，则非确定性算法表示源自多条路径的单一路径，其中一些路径可能到达相同的输出，而另一些路径可能到达唯一的输出。

什么使算法不确定？

多种因素可导致算法以不确定或不确定的方式运行：

• 如果它使用输入以外的外部状态，例如用户输入、全局变量、硬件计时器值、随机值或存储的磁盘数据。
• 如果它以对时间敏感的方式运行，例如，如果它有多个处理器同时写入同一数据。在这种情况下，每个处理器写入数据的精确顺序将影响结果。
• 如果硬件错误导致其状态以意外方式更改。

关于非确定性算法你需要知道什么

• 非确定性算法是指每个算法的结果都不是唯一定义的，并且结果可能是随机的算法。
• 在非确定性算法中，算法在每次执行中的执行路径都不相同，可以采用任意随机路径执行。
• 非确定性算法被归类为特定输入的非可靠算法。机器在不同执行时会给出不同的输出。
• 在非确定性算法中，允许执行每个操作的机器根据稍后定义的确定条件选择这些结果中的任何一个。
• 由于结果是未知的，并且在不同的执行上是不一致的，所以非确定性算法不能在多项式时间内执行。

Also Read: Difference Between NP Hard And NP Complete Problem

确定性(deterministic)和表格形式的非确定性算法(non-deterministic algorithms in tabular form)的区别