文章目录
一、计算理论内容概览
二、计算问题的判定性
三、计算问题的 有效性
四、时间复杂性度量
五、算法有效性 数学定义需求
六、输入表示
七、时间复杂度
一、计算理论内容概览
----
计算理论分为..., 都属于 形式语言 与 自动机 部分 ;
可计算 内容 : 图灵机 , 确定性图灵机 , 非确定性图灵机 , 丘奇-图灵命题 , 可判定性 , 可计算性 等问题 ;
计算复杂性 内容 : 时间复杂性...或 无效算法 ;
为 算法有效性 提供一个 严格的数学定义 ;
六、输入表示
----
输入字符串大小 , 输入字符串越长 , 所花的时间越长 , 计算所花的时间与输入字符串时单调递增的 ;
有效性...进行定义时 , 通过输入字符串大小进行度量 ;
计算机计算输入有很多形式 , 数字 , 图形 , 字符串 , 二进制数据 等 ;
数字的表示 , 假如输入数字是
17
, 要将对应的时间复杂度理解成...2
, 这个数字由
2
位数字组成的 ;
如果将上述
17
数字 , 使用二进制表示 , 是
10001
, 输入位数是
5
, 对应的时间复杂度理解成
5
;
算法复杂性 只与输入的数据大小有关