470
个编辑
更改
跳到导航
跳到搜索
第60行：
第60行： + + + + + + + + + + + + + +
柯氏复杂度补充定义
柯式复杂度的主要缺点是因为停机问题而导致的不可计算性，针对K式复杂度的主要评论是它高度依赖编程语言的选择。
柯式复杂度的主要缺点是因为停机问题而导致的不可计算性，针对K式复杂度的主要评论是它高度依赖编程语言的选择。
为提高通用性，忽略各图灵机之间的差异，将柯氏复杂度定义进一步定义为：
<math>
K(s) := C_U(x) = min\{ \lvert \lang M,w \rang \rvert): 图灵机M在输入w时停机并输出x \}
</math>
按照前式标准化为：
<math>
K(s) := C_U(x) = min\{ \lvert \lang M,w \rang \rvert): M(w) = x \}
</math>
这里的w等于前式的p，即输出x的代码字符串。
===统计复杂度===
===统计复杂度===