文章目录

一、时间复杂度时间单位

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

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

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

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

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

二、算法分析

给定语言 :A={0k1k:k≥0}\rm A = \{ 0^k1^k : k \geq 0 \}A={0k1k:k≥0}

构造图灵机 M1\rm M_1M1​ 认识上述语言 : 设计过程如下 :

在图灵机带子上放入 0k1k0^k1^k0k1k 字符 , 如 000111000111000111 , 如何识别该字符串 , 一定在 A\rm AA 语言中 ,

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

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

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

M1=\rm M_1 =M1​= "在长度为 n\rm nn 的字符串 w\rm ww 上进行如下计算 :

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

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

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

三、算法复杂性分析

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

最坏的情况就是在每个步骤中 , 都达到计算的最大值 , 最坏的情况就是 000 的个数与 111 的个数一样多 , 都是 n2\rm \cfrac{n}{2}2n​ 个 , 并且 000 在前面 , 111 在后面 , 这是计算步数最多的情况 ;

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