时间：2022-12-29 02:30:01 | 来源：信息时代
时间：2022-12-29 02:30:01 来源：信息时代
计算复杂性理论 : 用数学方法研究各类问题的计算复杂性的一门学科。它研究各种可计算问题在计算过程中资源消耗情况,以及在不同计算模型下,使用不同类型资源以及不同数量资源对各类问题复杂性的本质特性和相互关系。
在计算复杂性理论中资源主要指的是各类问题在计算过程中所占用的时间与空间资源。它与问题的计算规模n有关,亦即是说,算法所需时间、空间是问题规模n的函数T(n)和S(n)。
在时间复杂性的度量中,我们一般分成为两级,其中一级是多项式级时间算法,即T(n)呈多项式表示或是∪kO(nk),其中k为常量,另一级是指数级时间算法,T(n)呈指数表示或是∪kO(kn),其中k为常量。在这两级中算法执行时间有着本质上的不同。在多项式时间算法中,计算机计算能力的提高对问题计算规模可有明显增加,而在指数时间算法中,计算机计算能力的提高对问题计算规模几乎毫无影响。因此,我们说,凡是一问题有多项式时间算法则称该问题是易解的,并称它属于P类,反之,如一问题是指数时间算法则称该问题是难解的。寻找问题的多项式时间算法或证明该问题是难解的是计算复杂性理论中所研究的重要问题。同样的,对空间复杂性度量也有类似情况。一般认为凡是P类问题都是现实计算机上可解的问题,而难解的问题则是计算机所无法可解的问题。
在计算复杂性理论中还有一个重要而著名的研究课题,它即是P=? NP问题。在求解问题中,如果问题有不确定的多项式时间算法,则称它属NP类,NP类中最难解的问题称NP完全类,P类是否就等于NP类,是当代算法理论中最著名的未解决难题称P=?NP问题。目前在理论上取得的最大成果是只要证明有一个NP完全问题属于P类,那么一切NP类问题都将属于P类。此结论表明可以将一般性的问题解决化解成为个别特殊的问题解决。
计算复杂性理论对计算机科学以及数据库中的算法设计与分析起到了重大的作用。一般讲,任何一个计算机或数据库中的算法其复杂性应是P类,只有这样才能在现实计算机中获得解决。
关键词：数据,理论,复杂
在线咨询
