計算複雜性測度(computational complexitymeasure)簡稱複雜性測度，是對計算複雜性概念的一種定量刻畫。
基本介紹
- 中文名：計算複雜性測度
- 外文名：computational complexitymeasure
簡介
計算複雜性理論最關心的一個問題，是某個遞歸函式的計算過程或某個遞歸問題的判定過程到底有多複雜.為了回答這個問題，首先必須給出度量計算（或判定）過程之複雜性的標準.對此，有各種各樣可能的選擇.例如，在某種計算模型之下所化的計算步數或者所用到的空間等.這些都在一定程度上從某些特定的角度反映了計算(判定)過程的複雜程度.從而可以作為其複雜性測度。
從抽象的意義上來說，某個算法式輸入二後，其(收斂的)計算過程的複雜性測度可以是某個(具特定含義的)自然數，例如記為。p(x).這樣一來，對應於算法式的複雜性測度，實際上是一個函式xp(二).此函式稱為式的複雜性函式，其定義域恰好由使式收斂的輸入所組成.而其取值則在自然數中.如果假定某種算法的全體已被能行地列舉來:PoP, Pz…約定諸P是以自然數輸入的.那么其相應的複雜性測度便是一個函式列:a i Z…其中。(、)恰在式(n)收斂時有定義，而其值是算法式在輸入n後的計算複雜性度量(參見“布魯姆測度”). _ ; 。二便是一種計算複雜性測度.其中的每箇中都稱為複雜性函式.若中的定義依賴於所給的計算模型(如;(n)定義為計算步數或使用空等)，則稱中為面向模型的複雜性測度.否則便稱為與模型無關的。
