第四节．计算复杂性理论介绍内容摘要：
算法的计算复杂度 对问题的规模 n，确定循环次数。 对不确定的循环次数 估计最坏情况下的计算量（如 while 循环） 三、决策（判定）问题 判定问题就是回答“是”或“否”的问题。 和旅行商 问题相关的判定问题： 一个有穷的“城市”集合 C={1C ， 2C ,… , mC }. 对于任意一对城市 iC 、 jC ∈ C，有“距离” ),( ji CCd ，以及界限 （正整数集合）。 问：是否有 C 的一个旅行路线，全长不超过 B。 只考虑判定问题的原因是它在计算理论中有一个对应物“语言” 四、 P类问题 多项式时间算法，设某算法 C的时间复杂度是 )(nf ，其中 n 是问题规模，有 ))(()( npOnf ， )(np 是多项式函数，则称 C 算法是多项式时间算法。 即：时间复杂度函数是 ))(( npO 的算法 指数时间算法：时间复杂性函数不能表示成 ))(( npO 的算法（包括：nnlog ：非多项式函数，不是指数函数） P 类问题＝ {有多项式时间算法解决的判定问题 }。 举例：（ P 类问题）班上是否有年龄小于 20 的同学。 五、 NP（ Nondeterministic Polynomial）类问题 对于旅行商判定问题还没有找到解这个问题的多项式算法。 但如果回答“是”，我们如果怀疑就请他给一条这样的旅行路线经证实。 我们验证它是否是旅行路线，是否小于 B，如果回。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。