確定型時間複雜性測度

確定型時間複雜性測度(deterministic timecomplexity measure)一種複雜性測度.它是以計算步數為度量的複雜性測度。

基本介紹

• 中文名：確定型時間複雜性測度
• 外文名：deterministic timecomplexity measure

確定型時間複雜性測度(deterministic timecomplexity measure)一種複雜性測度.它是以計算步數為度量的複雜性測度.設M為(確定型)算法(計算模型).若字w輸人M後在n步收斂(停機).則稱n為M輸人W時的計算步數或計算長度.若M在輸人W後不收斂，則其計算時間無定義(或稱無窮大).若以。M( )表示M在輸人。時的計算時間，並為M的複雜性測度.則 M稱為M的時間複雜性測度.一般地，若把某種算法的全體枚舉出來:Mo,MMz,…並以中，表示 M作為從的時間複雜性測度.則中一 ifiE。便是關於這種算法的時間複雜性測度.時間複雜性測度中記為DTIME.設 M為算法M的時間複雜性測度.如令 'M＜n _max M＜cu W長度為n .則稱 ' M為M運行時間(函式)或時間複雜性函式.