文章目录
一、非确定性图灵机的时间复杂度
二、非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的指数关系
一、非确定性图灵机的时间复杂度
----
给定一个非确定性图灵机 , 该图灵机是 判定机 ,...\rm N
;
定义域 : 定义域中的自然数
\rm N
表示 输入字符串的大小 ,
值域 : 值域中的自然数
\rm N
表示 计算步数 ;
确定性图灵机 计算 , 与 非确定性图灵机...计算 的差别 :
确定性图灵机 在字符串上进行计算时 , 只有一个分支 , 非确定性图灵机 在字符串上进行计算时 , 有很多个分支 ;
非确定性图灵机 时间复杂度取值 : 将所有的长度为
\rm n...的字符串 , 依次输入到 非确定性图灵机 中进行计算 , 得到的计算树是不同的 , 所有的计算树中 , 高度最高的计算树的高度 , 作为计算的步数 , 也就是时间复杂度的取值 ;
二、非确定性图灵机...与 确定性图灵机 的时间复杂度 之间的指数关系
----
使用 确定性图灵机 , 模仿 非确定性图灵机 , 在 计算效率方面要付出一定的代价 , 计算复杂度会 指数级增加 ;
如果 非确定性 单个带子