1,068
个编辑
更改
跳到导航
跳到搜索
第70行：
第70行： − + −
→确定性模型
===确定性模型===
===确定性模型===
一个'''确定性模型 deterministic model '''的计算是一种机器的后续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，最早的确定性模型是'''[[递归]]函数 recursive functions'''、 '''lambda 演算 lambda calculus'''和'''[[图灵机]] Turing machines'''。'''随机存取机器 Random access machine '''(也称 RAM-machines)的模型也被广泛使用，更接近真实的'''计算机 computer'''。
一个'''确定性模型 deterministic model '''的计算是一种机器的后续状态和要执行的操作完全由前面的状态决定的计算模型。历史上，最早的确定性模型是'''[[递归]]函数 recursive functions'''、 '''lambda演算 lambda calculus'''和'''[[图灵机]] Turing machines'''。'''随机存取机器 Random access machine '''(也称 RAM-machines)的模型也被广泛使用，更接近真实的'''计算机 computer'''。
当计算模型没有被指定时，通常假设它是一个'''多带图灵机 multitape Turing machine'''。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以确保这种等价性.
当计算模型没有被指定时，通常假设它是一个'''多带图灵机 multitape Turing machine'''。对于大多数算法，在多带图灵机上的时间复杂度与在RAM-machines上的相同，尽管可能需要注意如何将数据存储在内存中，以确保这种等价性.
===非确定性计算===
===非确定性计算===