【计算理论】计算复杂性 ( 两个带子的图灵机的时间复杂度 | 证明多个带子图灵机时间复杂度 )

文章目录

• 一、确定性模型的计算复杂性关系
• 二、证明 "多个带子图灵机时间复杂度是

\rm O(n^2)

"

一、确定性模型的计算复杂性关系

---

计算的 复杂性 取决于 模型的计算 ;

给定一个函数

\rm t(n)

, 假设有一个 两个带子图灵机 时间复杂度是

\rm O(t(n))

, 那么对应的有相同计算能力的 一个带子图灵机 时间复杂度是

\rm O(t^2(n))

;

示例 : 参考上一篇博客 【计算理论】计算复杂性 ( 两个带子的图灵机的时间复杂度 ) , 识别语言

\rm A = \{ 0^k1^k : k \geq 0 \}

, 一个带子图灵机识别上述语言的 计算时间复杂度是

\rm O(n^2)

, 两个带子图灵机识别上述语言的 计算时间复杂度是

\rm O(n)

;

二、证明 "多个带子图灵机时间复杂度是

\rm O(n^2)

"

---

参考 【计算理论】图灵机 ( 多个带子的图灵机 | 计算能力对比 | 证明过程 | 一个带子图灵机 ) 博客 , 以如下三个带子的图灵机为例 , 加入下面的 三个带子图灵机的时间复杂度是

\rm t(n)

;

使用 单个带子图灵机 模仿上述 三个带子图灵机 , 那么对应的单个带子图灵机的时间复杂度是

\rm t^2(n)

;

计算 单个单子图灵机 模仿 三个带子图灵机 一步的计算 , 需要花费的步数 ;

模仿的核心是将三个带子的字符串放在一个带子中 , 使用 “#” 分割 , 并使用红色记录三个带子对应的位置 , 一个读头需要记录三个位置 , 如下图 :

使用

1

个带子的图灵机 模拟

3

个带子的图灵机 的代价是 读写头必须从左向右整个遍历一遍带子 , 才能模拟

3

个带子的图灵机 一步的计算 ;

最坏的情况下就是 , 三个带子图灵机走

1

步 , 单个带子图灵机走 三个带子所有字符串的内容长度 对应的步数 , 也就是

10 + 4

步 , 多出来的

4

步是

4

个 “#” 分割字符 ;

三个带子图灵机 每个带子的长度是

\rm t(n)

, 单个带子图灵机 带子长度是

\rm 3t(n)

;

单个带子图灵机 模仿 三个带子图灵机 一步操作 , 最坏的情况下 , 需要执行的步数是

\rm 3t(n)

;

总共需要模仿

\rm t(n)

步 , 因此总共需要模仿的步数是

\rm 3t^2(n)

;

如果是 四个带子图灵机 , 总共需要模仿的步数是

\rm 4t^2(n)

,

如果是 五个带子图灵机 , 总共需要模仿的步数是

\rm 5t^2(n)

,

如果是 一百个带子图灵机 , 总共需要模仿的步数是

\rm 100t^2(n)

,

其数量级还是

\rm t^2(n)

,

因此增加到

2

个带子 , 与 增加到

100

个带子 , 甚至 一亿个带子 , 算法复杂度的数量级是

\rm O(n^2)

, 这是不变的 ;

单个带子模仿多个带子图灵机 , 所花费的时间是平方增加 , 不管多个带子的个数是多少 ;