【计算理论】计算复杂性 ( 时间复杂度时间单位 : 步数 | 算法分析 | 算法复杂性分析 )

一、时间复杂度时间单位

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

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

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

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

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

二、算法分析

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

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

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

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

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

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

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

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

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

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

三、算法复杂性分析

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

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

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