文章目录
一、确定性模型的计算复杂性关系
二、证明 "多个带子图灵机时间复杂度是 O ( n 2 ) \rm O(n^2)O(n
2
)"
一、确定性模型的计算复杂性关系
计算的 复杂性 取决于 模型的计算 ;
给定一个函数 t ( n ) \rm t(n)t(n) , 假设有一个 两个带子图灵机 时间复杂度是 O ( t ( n ) ) \rm O(t(n))O(t(n)) , 那么对应的有相同计算能力的 一个带子图灵机 时间复杂度是 O ( t 2 ( n ) ) \rm O(t^2(n))O(t
2
(n)) ;
示例 : 参考上一篇博客 【计算理论】计算复杂性 ( 两个带子的图灵机的时间复杂度 ) , 识别语言 A = { 0 k 1 k : k ≥ 0 } \rm A = \{ 0^k1^k : k \geq 0 \}A={0
k
1
k
:k≥0} , 一个带子图灵机识别上述语言的 计算时间复杂度是 O ( n 2 ) \rm O(n^2)O(n
2
) , 两个带子图灵机识别上述语言的 计算时间复杂度是 O ( n ) \rm O(n)O(n) ;
二、证明 "多个带子图灵机时间复杂度是 O ( n 2 ) \rm O(n^2)O(n
2
)"
参考 【计算理论】图灵机 ( 多个带子的图灵机 | 计算能力对比 | 证明过程 | 一个带子图灵机 ) 博客 , 以如下三个带子的图灵机为例 , 加入下面的 三个带子图灵机的时间复杂度是 t ( n ) \rm t(n)t(n) ;
使用 单个带子图灵机 模仿上述 三个带子图灵机 , 那么对应的单个带子图灵机的时间复杂度是 t 2 ( n ) \rm t^2(n)t
2
(n) ;
计算 单个单子图灵机 模仿 三个带子图灵机 一步的计算 , 需要花费的步数 ;
模仿的核心是将三个带子的字符串放在一个带子中 , 使用 “#” 分割 , 并使用红色记录三个带子对应的位置 , 一个读头需要记录三个位置 , 如下图 :
使用 1 11 个带子的图灵机 模拟 3 33 个带子的图灵机 的代价是 读写头必须从左向右整个遍历一遍带子 , 才能模拟 3 33 个带子的图灵机 一步的计算 ;
最坏的情况下就是 , 三个带子图灵机走 1 11 步 , 单个带子图灵机走 三个带子所有字符串的内容长度 对应的步数 , 也就是 10 + 4 10 + 410+4 步 , 多出来的 4 44 步是 4 44 个 “#” 分割字符 ;
三个带子图灵机 每个带子的长度是 t ( n ) \rm t(n)t(n) , 单个带子图灵机 带子长度是 3 t ( n ) \rm 3t(n)3t(n) ;
单个带子图灵机 模仿 三个带子图灵机 一步操作 , 最坏的情况下 , 需要执行的步数是 3 t ( n ) \rm 3t(n)3t(n) ;
总共需要模仿 t ( n ) \rm t(n)t(n) 步 , 因此总共需要模仿的步数是 3 t 2 ( n ) \rm 3t^2(n)3t
2
(n) ;
如果是 四个带子图灵机 , 总共需要模仿的步数是 4 t 2 ( n ) \rm 4t^2(n)4t
2
(n) ,
如果是 五个带子图灵机 , 总共需要模仿的步数是 5 t 2 ( n ) \rm 5t^2(n)5t
2
(n) ,
如果是 一百个带子图灵机 , 总共需要模仿的步数是 100 t 2 ( n ) \rm 100t^2(n)100t
2
(n) ,
其数量级还是 t 2 ( n ) \rm t^2(n)t
2
(n) ,
因此增加到 2 22 个带子 , 与 增加到 100 100100 个带子 , 甚至 一亿个带子 , 算法复杂度的数量级是 O ( n 2 ) \rm O(n^2)O(n
2
) , 这是不变的 ;
单个带子模仿多个带子图灵机 , 所花费的时间是平方增加 , 不管多个带子的个数是多少 ;
