文章目录
一、两个带子的图灵机的时间复杂度
一、两个带子的图灵机的时间复杂度
讨论两个带子的图灵机的时间复杂度 ;
计算问题如下 :
给定语言 : A = { 0 k 1 k : k ≥ 0 } \rm A = \{ 0^k1^k : k \geq 0 \}A={0
k
1
k
:k≥0}
构造 两个带子的 图灵机 M 3 \rm M_3M
3
认识上述语言 ;
算法分析过程 : 假设字符串为 000111 000111000111 , 最坏的情况 ;
开始时的状态 : 第一个带子是 000111 000111000111 输入字符 , 第二个带子是空的 ;
第一步 : 读头一 读取 带子一 字符 0 00 , 读头二 将 0 00 字符写入到 带子二 中 ;
第二步 : 读头一 读取 带子一 字符 0 00 , 读头二 将 0 00 字符写入到 带子二 中 ;
第三步 : 读头一 读取 带子一 字符 0 00 , 读头二 将 0 00 字符写入到 带子二 中 ;
第四步 : 读头一 读取 带子一 字符 1 11 , 读头二 将 0 00 字符从当前带子中抹掉 ;
第五步 : 读头一 读取 带子一 字符 1 11 , 读头二 将 0 00 字符从当前带子中抹掉 ;
第六步 : 读头一 读取 带子一 字符 1 11 , 读头二 将 0 00 字符从当前带子中抹掉 ; 此时带子一读取完毕 , 带子二为空 , 此时进入接受状态 ;
M 3 \rm M_3M
3
是两个带子的图灵机 , 算法设计如下 :
M 3 = \rm M_3 =M
3
= " 在输入字符串 w \rm ww 上进行如下计算 :
① 扫描整个带子上的字符串 , 查看 0 00 和 1 11 的顺序 , 所有的 0 00 必须在所有的 1 11 前面 ; 如果顺序错误 , 进入 拒绝状态 ;
② 扫描 带子一 上的 0 00 字符 , 直到遇到 1 11 字符 , 同时将 0 00 拷贝到 带子二 中 ;
③ 扫描 带子一 上的 1 11 字符 , 直到字符串结束 , 每读取一个 1 11 字符 , 就删除 带子二 中的 0 00 字符 ;
④ 如果所有的 0 00 字符都被删除 , 带子一 中的 1 11 字符还没有读取完毕 , 进入 拒绝状态 ; 如果 带子一 中的字符读取完毕 , 带子二 中还有 0 00 字符剩余 , 进入 拒绝状态 ; 如果 带子二 中的 0 00 字符都被删除 , 带子一 正好读取完毕 , 进入 接受状态 ; "
计算上述算法的时间复杂度 :
首先检查 01 0101 的相对顺序 , 最坏的情况下是读头走 n \rm nn 步 , 其复杂度是 O ( n ) \rm O(n)O(n) ;
然后读取带子一 然后写入擦除带子二 操作 , 整体执行了 n \rm nn 步 , 的时间复杂度是 O ( n ) \rm O(n)O(n)
上述两个步骤的时间复杂度是 : O ( n ) + O ( n ) = O ( n ) \rm O(n) + O(n) = O(n)O(n)+O(n)=O(n)
在 【计算理论】计算复杂性 ( 小 O 记号 | 严格渐进上界 | 分析算法的时间复杂度 ) 博客中 , 使用一个带子的图灵机 M 1 \rm M_1M
1
识别上述语言 , 时间复杂度是 O ( n ) + O ( n 2 ) = O ( n 2 ) \rm O(n) + O(n^2) = O(n^2)O(n)+O(n
2
)=O(n
2
) ;
两个带子的图灵机 与 一个带子的图灵机 计算能力 是等价的 ,
计算能力 等价 指的是 可以 识别相同的语言 , 解决相同的计算问题 ,
但是两种图灵机的 计算效率不同 , 两个带子的图灵机计算效率一般 高于 一个带子的图灵机的计算效率 ;
