【计算理论】计算复杂性 ( 计算理论内容概览 | 计算问题的有效性 | 时间复杂性度量 | 输入表示 | 时间复杂度 )

文章目录

• 一、计算理论内容概览
• 二、计算问题的判定性
• 三、计算问题的 有效性
• 四、时间复杂性度量
• 五、算法有效性 数学定义需求
• 六、输入表示
• 七、时间复杂度

一、计算理论内容概览

计算理论分为 形式语言与自动机 , 可计算部分 , 计算复杂性部分 ;

形式语言与自动机 内容 : 自动机 , 确定性有限自动机 , 非确定性有限自动机 , 正则语言 , 泵引理 , 上下文无关语法 , 下推自动机 , 都属于 形式语言 与 自动机 部分 ;

可计算 内容 : 图灵机 , 确定性图灵机 , 非确定性图灵机 , 丘奇-图灵命题 , 可判定性 , 可计算性 等问题 ;

计算复杂性 内容 : 时间复杂性 , 模型间的时间复杂性关系 ,

类 ,

类 ;

计算理论 知识点很枯燥 , 但是 在进行理论研究时 , 或者大的计算机工程实践时 , 很有用 ;

二、计算问题的判定性

根据计算模型 , 可以将判定性问题 , 总结成以下几点 :

① 所有 关于 图灵机 的计算问题 , 都是 不可判定的 ; ( 莱斯定理 )

② 所有 关于 确定性有限自动机 的计算问题 , 都是可判定的 ;

③ 关于 下推自动机 的计算问题 , 有些可判定 , 有些不可判定 ;

三、计算问题的 有效性

可计算性 包含 可判定性 , 可判定性 包含 有效性 ;

可计算性 > 可判定性 > 有效性 ;

计算问题 对应的算法中 , 有些算法是 有效的 , 有些算法是 无效的 ,

如 : 穷举算法 , 蛮力搜索之类的算法 , 没有有效性可言 , 肯定不是有效算法 ; 贪心算法 , 欧几里得算法 是有效算法 ;

这里希望可以区分 有效算法 与 无效算法 ;

四、时间复杂性度量

计算机中度量时间长短有两种方式 :

① 离散时间 ( 自然数表达 ) : 时间是离散的 , 如

秒

② 连续时间 ( 实数表达 ) : 时间是连续的 , 如

秒

计算复杂性的表达使用的是 离散时间 , 自然数表达 ;

五、算法有效性 数学定义需求

有效性 与 无效性 区分时 , 将 贪心算法 分到有效性算法中 , 将蛮力穷举的算法 分到无效性算法中 ;

需要定一个区分原则 , 区分算法的有效性 , 将一个算法分为 有效算法 或 无效算法 ;

为 算法有效性 提供一个 严格的数学定义 ;

六、输入表示

输入字符串大小 , 输入字符串越长 , 所花的时间越长 , 计算所花的时间与输入字符串时单调递增的 ;

有效性 进行定义时 , 通过输入字符串大小进行度量 ;

计算机计算输入有很多形式 , 数字 , 图形 , 字符串 , 二进制数据 等 ;

数字的表示 , 假如输入数字是

, 要将对应的时间复杂度理解成

, 这个数字由

位数字组成的 ;

如果将上述

数字 , 使用二进制表示 , 是

, 输入位数是

, 对应的时间复杂度理解成

;

算法复杂性 只与输入的数据大小有关 , 输入的大小必须是合理的 ;

输入数字时 , 可以输入 十六进制 , 十进制 , 八进制 , 二进制 , 但是不能输入 一进制数字 , 一进制输入是不合理的 ;

七、时间复杂度

假设

是 确定性图灵机 , 该图灵机在所有的输入上都会 停机 ;

因为该图灵机会停机 , 其结果不是接受 , 就是拒绝 , 不会出现 Loop 不停机的状态 , 因此该 图灵机

是判定机 ;

图灵机

的运行时间 或 时间复杂度 是一个函数

, 该函数是 从 自然数集 到 自然数集上的映射 ,

;

前面的自然数集

主要是度量的 输入字符串大小 , 后面的自然数集

是计算的步数 ;

的含义是度量 长度为

的所有字符串 , 计算时所花费的步数的 最大值 ;

证明

为什么必须是判定机 :

假设

是图灵机 , 在某些输入上是不停机的 , 如输入字符串为

;

图灵机

在

字符串上进行计算时 , 进入 Loop 状态 , 不停机 , 此时定义

的值只能是无穷大 ;

此时该函数

就没有意义了 ;

函数在数字上进行取值时 , 必须是一个具体的数字 ;