文章目录
一、时间复杂度时间单位
二、算法分析
三、算法复杂性分析
一、时间复杂度时间单位
图灵机计算时间 是根据 步数 进行定义的 , 图灵机走 1 11 步 , 时间加一 ,
每一步的时间可能不一致 , 有些步需要花费少量时间 , 有些步需要花费大量时间 ,
在计算理论中 , 只讨论步数 , 不讨论具体精确的时间 ;
f ( n ) \rm f(n)f(n) 是长度为 n \rm nn 的字符串 , 输入到图灵机中进行计算时 , 所需要的 步数的最大值 ;
步数的最大值就是最坏情况下走的最多的步数 ;
二、算法分析
给定语言 : A = { 0 k 1 k : k ≥ 0 } \rm A = \{ 0^k1^k : k \geq 0 \}A={0
k
1
k
:k≥0}
构造图灵机 M 1 \rm M_1M
1
认识上述语言 : 设计过程如下 :
在图灵机带子上放入 0 k 1 k 0^k1^k0
k
1
k
字符 , 如 000111 000111000111 , 如何识别该字符串 , 一定在 A \rm AA 语言中 ,
首先检查 01 0101 的相对顺序 , 0 00 一定要出现在 1 11 的前面 , 如果顺序紊乱就进入拒绝状态 , 如果顺序正确 , 继续向下执行 ;
每遇到一个 0 00 就划掉一个 1 11 , 如果最后发现都没有剩余 , 那么该图灵机进入接受状态 , 否则进入拒绝状态 ;
M 1 \rm M_1M
1
图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;
M 1 = \rm M_1 =M
1
= "在长度为 n \rm nn 的字符串 w \rm ww 上进行如下计算 :
① 扫描整个带子上的字符串 , 查看 0 00 和 1 11 的顺序 , 所有的 0 00 必须在所有的 1 11 前面 ; 如果顺序错误 , 进入拒绝状态 ;
② 扫描整个带子 , 遇到一个 0 00 , 就划掉一个 1 11 ; 如果带子上存在 0 00 和 1 11 , 该操作重复进行 ;
③ 如果最后只剩下 0 00 或只剩下 1 11 , 说明 两个数字的个数不等 , 进入拒绝状态 ; 如果最后带子上只剩下空白字符 , 说明两个数字个数相等 , 进入接受状态 ; "
三、算法复杂性分析
现在讨论上述算法的复杂性 , 假设给定字符串长度为 n \rm nn , 那么讨论在最坏的情况下 , 所花费的时间最大值 ;
最坏的情况就是在每个步骤中 , 都达到计算的最大值 , 最坏的情况就是 0 00 的个数与 1 11 的个数一样多 , 都是 n 2 \rm \cfrac{n}{2}
2
n
个 , 并且 0 00 在前面 , 1 11 在后面 , 这是计算步数最多的情况 ;
如 : 第一步如果 1 11 就出现在第一个 , 执行 1 11 步就进入了拒绝状态 , 此时肯定是最少的执行步数 ;
