307
个编辑
更改
跳到导航
跳到搜索
第152行：
第152行： − + 第160行：
第160行： − 当计算模型没有被指定时，通常假设它是一个多带图灵机。对于大多数算法，在多带图灵机上的时间复杂度与在 ram 机上的相同，尽管可能需要在数据如何存储在内存中以获得这种等价性方面进行一些注意。+ − −
→Deterministic models
A deterministic model of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were recursive functions, lambda calculus, and Turing machines. The model of Random access machines (also called RAM-machines) is also widely used, as a closer counterpart to real computers.
A deterministic model of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were recursive functions, lambda calculus, and Turing machines. The model of Random access machines (also called RAM-machines) is also widely used, as a closer counterpart to real computers.
一个'''<font color="#ff8000">确定性模型 deterministic model </font>'''的计算是一种机器的连续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，第一个确定性模型是'''<font color="#ff8000">递归函数 recursive functions</font>'''、 '''<font color="#ff8000">lambda 演算 lambda calculus</font>'''和'''<font color="#ff8000">图灵机 Turing machines</font>'''。'''<font color="#ff8000">随机存取机器 Random access machine </font>'''(也称 RAM-machines)的模型也被广泛使用，作为更接近真实'''<font color="#ff8000">计算机 computer</font>'''的对应物。
一个'''<font color="#ff8000">确定性模型 deterministic model </font>'''的计算是一种机器的连续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，第一个确定性模型是'''<font color="#ff8000">递归函数 recursive functions</font>'''、 '''<font color="#ff8000">lambda 演算 lambda calculus</font>'''和'''<font color="#ff8000">图灵机 Turing machines</font>'''。'''<font color="#ff8000">随机存取机器 Random access machine </font>'''(也称 RAM-machines)的模型也被广泛使用，更接近真实的'''<font color="#ff8000">计算机 computer</font>'''。
When the model of computation is not specified, it is generally assumed to be a multitape Turing machine. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence.
When the model of computation is not specified, it is generally assumed to be a multitape Turing machine. For most algorithms, the time complexity is the same on multitape Turing machines as on RAM-machines, although some care may be needed in how data is stored in memory to get this equivalence.
当计算模型没有被指定时，通常假设它是一个'''<font color="#ff8000">多带图灵机 multitape Turing machine</font>'''。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以获得这种等价性.
===Non-deterministic computation===
===Non-deterministic computation===