文章目录
一、计算理论内容概览
二、计算问题的判定性
三、计算问题的 有效性
四、时间复杂性度量
五、算法有效性 数学定义需求
六、输入表示
七、时间复杂度
一、计算理论内容概览
----
计算理论分为...都是可判定的 ;
③ 关于 下推自动机 的计算问题 , 有些可判定 , 有些不可判定 ;
三、计算问题的 有效性
----
可计算性 包含 可判定性 , 可判定性 包含 有效性 ;
可计算性 > 可判定性...是有效算法 ;
这里希望可以区分 有效算法 与 无效算法 ;
四、时间复杂性度量
----
计算机中度量时间长短有两种方式 :
① 离散时间 ( 自然数表达 ) : 时间是离散的 , 如
1, 2,...进行定义时 , 通过输入字符串大小进行度量 ;
计算机计算输入有很多形式 , 数字 , 图形 , 字符串 , 二进制数据 等 ;
数字的表示 , 假如输入数字是
17
, 要将对应的时间复杂度理解成...主要是度量的 输入字符串大小 , 后面的自然数集
\rm N
是计算的步数 ;
\rm f(n)
的含义是度量 长度为
\rm n
的所有字符串 , 计算时所花费的步数的 最大值 ;
证明