确定性算法的例子？

Question

晚上好,我想知道是否有人可以请我提供一个确定性算法的简单伪代码示例......我将非常感激它并且肯定会给你积分!! 谢谢

Answer 1

对我而言,"确定性"可能意味着许多事情:

• 给定相同的输入,每次产生相同的输出.
• 给定相同的输入,每次运行时需要相同的时间/内存/资源.
• 复杂性类的问题P可以通过确定性计算机在多项式时间内解决,而不是复杂性类的问题,NP其可以仅使用非确定性计算机在多项式时间内求解.

你是说什么意思？

最简单的确定性算法是这个随机数发生器.

def random():
    return 4 #chosen by fair dice roll, guaranteed to be random

它每次都提供相同的输出,展示已知的O(1)时间和资源使用,并在PTIME任何计算机上执行.