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

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

给定一个函数 $\mathrm{t}(\mathrm{n})$ , 假设有一个 两个带子图灵机 时间复杂度是 $\mathrm{O}(\mathrm{t}(\mathrm{n}))$ , 那么对应的有相同计算能力的 一个带子图灵机 时间复杂度是 $\mathrm{O}({\mathrm{t}}^2(\mathrm{n}))$ ;

示例 : 参考上一篇博客 【计算理论】计算复杂性 ( 两个带子的图灵机的时间复杂度 ) , 识别语言 $\mathrm{A}=\{0^{\mathrm{k}}{1}^{\mathrm{k}}:\mathrm{k}\ge 0\}$ , 一个带子图灵机识别上述语言的 计算时间复杂度是 $\mathrm{O}({\mathrm{n}}^2)$ , 两个带子图灵机识别上述语言的 计算时间复杂度是 $\mathrm{O}(\mathrm{n})$ ;

二、证明 "多个带子图灵机时间复杂度是 $\mathrm{O}({\mathrm{n}}^2)$"

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

使用 单个带子图灵机 模仿上述 三个带子图灵机 , 那么对应的单个带子图灵机的时间复杂度是 ${\mathrm{t}}^2(\mathrm{n})$ ;

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

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

使用 $1$ 个带子的图灵机 模拟 $3$ 个带子的图灵机 的代价是 读写头必须从左向右整个遍历一遍带子 , 才能模拟 $3$ 个带子的图灵机 一步的计算 ;

最坏的情况下就是 , 三个带子图灵机走 $1$ 步 , 单个带子图灵机走 三个带子所有字符串的内容长度 对应的步数 , 也就是 $10+4$ 步 , 多出来的 $4$ 步是 $4$ 个 “#” 分割字符 ;

三个带子图灵机 每个带子的长度是 $\mathrm{t}(\mathrm{n})$ , 单个带子图灵机 带子长度是 $3\mathrm{t}(\mathrm{n})$ ;

单个带子图灵机 模仿 三个带子图灵机 一步操作 , 最坏的情况下 , 需要执行的步数是 $3\mathrm{t}(\mathrm{n})$ ;

总共需要模仿 $\mathrm{t}(\mathrm{n})$ 步 , 因此总共需要模仿的步数是 $3{\mathrm{t}}^2(\mathrm{n})$ ;

如果是 四个带子图灵机 , 总共需要模仿的步数是 $4{\mathrm{t}}^2(\mathrm{n})$ ,

如果是 五个带子图灵机 , 总共需要模仿的步数是 $5{\mathrm{t}}^2(\mathrm{n})$ ,

如果是 一百个带子图灵机 , 总共需要模仿的步数是 $100{\mathrm{t}}^2(\mathrm{n})$ ,

其数量级还是 ${\mathrm{t}}^2(\mathrm{n})$ ,

因此增加到 $2$ 个带子 , 与 增加到 $100$ 个带子 , 甚至 一亿个带子 , 算法复杂度的数量级是 $\mathrm{O}({\mathrm{n}}^2)$ , 这是不变的 ;

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

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111108407