本页使用了标题或全文手工转换

计算模型 (数学)

维基百科,自由的百科全书
跳转至: 导航搜索

可计算性理论計算複雜性理論中,计算模型model of computation)是计算中允许使用的运算集及各自成本的定义。它是用于测量一个算法执行时间和/或内存空间上的复杂度。通过假定一个计算模型,可能分析出所需的计算资源或讨论算法或计算机的限制。

模型[编辑]

模型例如:

使用[编辑]

算法的运行时分析领域,它通常用于定义一个具有单位成本运算的计算模型,或者只有单位成本运算。 一个常见例子是隨機存取機器,它具有读取和写入其所有存储单元的单位成本。在这方面,它与上述图灵机模型不同。

模型驱动工程英语Model-driven engineering中,计算模型解释了整个系统的行为,包括每个组件的行为与结果。

一个经常被忽略的关键点是,被公布的问题的下限经常是由比实践中可使用的运算集更不受限制的计算模型得出,因而可能天真地存在还会有更快算法的想法。[1]

分类[编辑]

有着许多计算模型,它们在容许的运算集和它们的计算成本方面存在不同。它们可以被分为几大类:抽象機器和相当于它的模型(例如Λ演算相当于图灵机),用于可计算性的证明和算法计算复杂性的上限;还有决策树模型英语Decision tree model,用于证明算法问题计算复杂度的下限。

参见[编辑]

参考资料[编辑]

  1. ^ Examples of the price of abstraction?, cstheory.stackexchange.com

拓展阅读[编辑]