计算复杂性

来自计算思维百科
跳转至: 导航搜索

算法复杂性是针对特定算法而言的,而计算复杂性则是针对特定问题而言的,后者反映的是问题的固有难度。计算复杂性等于最佳的算法复杂性,它在计算科学中既有理论意义,又有实用价值。

计算复杂性是利用计算机求解问题的难易程度。其度量标准:一是计算所需的步数或指令条数(即时间复杂度),二是计算所需的存储空间大小(即空间复杂度)。当然没有必要就一个一个具体问题去研究它的计算复杂性,而是依据问题的难度去研究各种计算问题之间的联系。

一个问题的规模是指这个问题的大小。一个算法的计算复杂性直接决定了这个算法可以用到多大规模的问题上。假设有求解同一个问题的两个算法,第一个算法的计算复杂性是n3,第二个算法的计算复杂性是3n。用每秒百万次的计算机来计算,当n=60时,第一个算法只要用时0.2秒,而第二个算法就要用时4×1028秒,也就是1015年,相当于10亿台每秒百万次的计算机计算一百万年。

考察上面提到的两个算法复杂性,前者n3是一个多项式函数,后者3n是一个指数函数。当n很大时,这两个算法的效率差别是很大的。因此,一个问题如果没有多项式时间计算复杂性的算法,这一问题就被称为是难解型问题。但是,要断定一个问题是否是难解型问题也是很困难的。一个问题即使长期没有找到多项式时间计算复杂性算法,也不能保证明天就一定找不到,更不能据此证明这个问题不存在多项式时间计算复杂性算法。