计算模型

计算机科学,更具体地说,在计算理论计算复杂性理论中,计算模型是一个模型,它描述了如何计算给定输入的数学函数的输出。一个模型描述了如何组织计算,记忆和通信的单位。在计算模型的情况下,可以测量算法计算复杂性。使用模型可以独立于特定的特定实现和特定技术的变化来研究算法的性能。

楷模

计算模型可以分为三类:顺序模型,功能模型和并发模型。

顺序模型

顺序模型包括:

功能模型

功能模型包括:

并发模型

并发模型包括:

其中一些模型既具有确定性非确定性变体。非确定模型对于实际计算没有用。它们用于研究算法的计算复杂性

模型的表现力有所不同。例如,也可以通过图灵机器计算有限状态计算机计算的每个功能,反之亦然。

用途

算法的运行时分析领域中,通常根据允许具有单位成本或简单单位成本操作原始操作指定计算模型。一个常用的示例是随机访问机,该计算机的单位成本用于读写和写入其所有存储单元。在这方面,它与上述图灵机模型不同。

也可以看看