文章目录
一、计算理论内容概览
二、计算问题的判定性
三、计算问题的 有效性
四、时间复杂性度量
五、算法有效性 数学定义需求
六、输入表示
七、时间复杂度
一、计算理论内容概览
计算理论分为 形式语言与自动机 , 可计算部分 , 计算复杂性部分 ;
形式语言与自动机 内容 : 自动机 , 确定性有限自动机 , 非确定性有限自动机 , 正则语言 , 泵引理 , 上下文无关语法 , 下推自动机 , 都属于 形式语言 与 自动机 部分 ;
可计算 内容 : 图灵机 , 确定性图灵机 , 非确定性图灵机 , 丘奇-图灵命题 , 可判定性 , 可计算性 等问题 ;
计算复杂性 内容 : 时间复杂性 , 模型间的时间复杂性关系 , P \rm PP 类 , N P \rm NPNP 类 ;
计算理论 知识点很枯燥 , 但是 在进行理论研究时 , 或者大的计算机工程实践时 , 很有用 ;
二、计算问题的判定性
根据计算模型 , 可以将判定性问题 , 总结成以下几点 :
① 所有 关于 图灵机 的计算问题 , 都是 不可判定的 ; ( 莱斯定理 )
② 所有 关于 确定性有限自动机 的计算问题 , 都是可判定的 ;
③ 关于 下推自动机 的计算问题 , 有些可判定 , 有些不可判定 ;
三、计算问题的 有效性
可计算性 包含 可判定性 , 可判定性 包含 有效性 ;
可计算性 > 可判定性 > 有效性 ;
计算问题 对应的算法中 , 有些算法是 有效的 , 有些算法是 无效的 ,
如 : 穷举算法 , 蛮力搜索之类的算法 , 没有有效性可言 , 肯定不是有效算法 ; 贪心算法 , 欧几里得算法 是有效算法 ;
这里希望可以区分 有效算法 与 无效算法 ;
四、时间复杂性度量
计算机中度量时间长短有两种方式 :
① 离散时间 ( 自然数表达 ) : 时间是离散的 , 如 1 , 2 , 3 , 4 , ⋯ 1, 2, 3, 4 , \cdots1,2,3,4,⋯ 秒
② 连续时间 ( 实数表达 ) : 时间是连续的 , 如 1.221457 ⋯ 1.221457\cdots1.221457⋯ 秒
计算复杂性的表达使用的是 离散时间 , 自然数表达 ;
五、算法有效性 数学定义需求
有效性 与 无效性 区分时 , 将 贪心算法 分到有效性算法中 , 将蛮力穷举的算法 分到无效性算法中 ;
需要定一个区分原则 , 区分算法的有效性 , 将一个算法分为 有效算法 或 无效算法 ;
为 算法有效性 提供一个 严格的数学定义 ;
六、输入表示
输入字符串大小 , 输入字符串越长 , 所花的时间越长 , 计算所花的时间与输入字符串时单调递增的 ;
有效性 进行定义时 , 通过输入字符串大小进行度量 ;
计算机计算输入有很多形式 , 数字 , 图形 , 字符串 , 二进制数据 等 ;
数字的表示 , 假如输入数字是 17 1717 , 要将对应的时间复杂度理解成 2 22 , 这个数字由 2 22 位数字组成的 ;
如果将上述 17 1717 数字 , 使用二进制表示 , 是 10001 1000110001 , 输入位数是 5 55 , 对应的时间复杂度理解成 5 55 ;
算法复杂性 只与输入的数据大小有关 , 输入的大小必须是合理的 ;
输入数字时 , 可以输入 十六进制 , 十进制 , 八进制 , 二进制 , 但是不能输入 一进制数字 , 一进制输入是不合理的 ;
七、时间复杂度
假设 M \rm MM 是 确定性图灵机 , 该图灵机在所有的输入上都会 停机 ;
因为该图灵机会停机 , 其结果不是接受 , 就是拒绝 , 不会出现 Loop 不停机的状态 , 因此该 图灵机 M \rm MM 是判定机 ;
图灵机 M \rm MM 的运行时间 或 时间复杂度 是一个函数 f \rm ff , 该函数是 从 自然数集 到 自然数集上的映射 , N → N \rm N \to NN→N ;
前面的自然数集 N \rm NN 主要是度量的 输入字符串大小 , 后面的自然数集 N \rm NN 是计算的步数 ;
f ( n ) \rm f(n)f(n) 的含义是度量 长度为 n \rm nn 的所有字符串 , 计算时所花费的步数的 最大值 ;
证明 M \rm MM 为什么必须是判定机 :
假设 M \rm MM 是图灵机 , 在某些输入上是不停机的 , 如输入字符串为 a a b \rm aabaab ;
图灵机 M \rm MM 在 a a b \rm aabaab 字符串上进行计算时 , 进入 Loop 状态 , 不停机 , 此时定义 f ( 3 ) \rm f(3)f(3) 的值只能是无穷大 ;
此时该函数 f ( n ) \rm f(n)f(n) 就没有意义了 ;
函数在数字上进行取值时 , 必须是一个具体的数字 ;
