一、时间复杂度时间单位

图灵机计算时间 是根据 步数 进行定义的 , 图灵机走 $1$ 步 , 时间加一 ,

每一步的时间可能不一致 , 有些步需要花费少量时间 , 有些步需要花费大量时间 ,

在计算理论中 , 只讨论步数 , 不讨论具体精确的时间 ;

$\mathrm{f}(\mathrm{n})$ 是长度为 $\mathrm{n}$ 的字符串 , 输入到图灵机中进行计算时 , 所需要的 步数的最大值 ;

步数的最大值就是最坏情况下走的最多的步数 ;

二、算法分析

给定语言 : $\mathrm{A}=\{0^{\mathrm{k}}{1}^{\mathrm{k}}:\mathrm{k}\ge 0\}$

构造图灵机 ${\mathrm{M}}_1$ 认识上述语言 : 设计过程如下 :

在图灵机带子上放入 $0^k{1}^k$ 字符 , 如 $000111$ , 如何识别该字符串 , 一定在 $\mathrm{A}$ 语言中 ,

首先检查 $01$ 的相对顺序 , $0$ 一定要出现在 $1$ 的前面 , 如果顺序紊乱就进入拒绝状态 , 如果顺序正确 , 继续向下执行 ;

每遇到一个 $0$ 就划掉一个 $1$ , 如果最后发现都没有剩余 , 那么该图灵机进入接受状态 , 否则进入拒绝状态 ;

${\mathrm{M}}_1$ 图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;

${\mathrm{M}}_1=$ "在长度为 $\mathrm{n}$ 的字符串 $\mathrm{w}$ 上进行如下计算 :

① 扫描整个带子上的字符串 , 查看 $0$ 和 $1$ 的顺序 , 所有的 $0$ 必须在所有的 $1$ 前面 ; 如果顺序错误 , 进入拒绝状态 ;

② 扫描整个带子 , 遇到一个 $0$ , 就划掉一个 $1$ ; 如果带子上存在 $0$ 和 $1$ , 该操作重复进行 ;

③ 如果最后只剩下 $0$ 或只剩下 $1$ , 说明 两个数字的个数不等 , 进入拒绝状态 ; 如果最后带子上只剩下空白字符 , 说明两个数字个数相等 , 进入接受状态 ; "

三、算法复杂性分析

现在讨论上述算法的复杂性 , 假设给定字符串长度为 $\mathrm{n}$ , 那么讨论在最坏的情况下 , 所花费的时间最大值 ;

最坏的情况就是在每个步骤中 , 都达到计算的最大值 , 最坏的情况就是 $0$ 的个数与 $1$ 的个数一样多 , 都是 $\frac{\mathrm{n}}{2}$ 个 , 并且 $0$ 在前面 , $1$ 在后面 , 这是计算步数最多的情况 ;

如 : 第一步如果 $1$ 就出现在第一个 , 执行 $1$ 步就进入了拒绝状态 , 此时肯定是最少的执行步数 ;

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

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