Remove ads

可计算性理论计算复杂性理论中,计算模型model of computation)描述了如何根据一组输入值计算函数的输出[1],包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量算法计算复杂度,总结出算法的性能,而不受特定技术和实现方式的性能差异所误导。

模型

计算模型可分为三大类:顺序模型、函数式模型以及同步模型。

顺序模型

顺序模型包括

函数式模型

函数式模型包括

同步模型

同步模型包括

各模型的表现不尽相同;例如,有限状态机可以计算的函数,图灵机也可以计算,反之亦然。

使用

算法分析领域,定义一个计算模型通常用具有单位成本的原始操作(也称单位成本操作)。一个常见例子是随机存取机器,任何存储单元的读写访问,都有着单位成本。在这方面,它与图灵机模型不同。

模型驱动工程中,计算模型解释了整个系统的行为是如何由每个组件的行为所共同造成的。

一个经常被忽略的关键点是,一些已知计算复杂度下限的问题是由较为局限的运算集得出的,实践中可使用的运算集可能更加广泛而强大,因而一些算法的实际性能,可能比高度抽象的计算模型得出的结果要好。[2]

分类

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

参见

参考资料

拓展阅读

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads