確定型時間複雜性測度

確定型時間複雜性測度(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運行時間(函式)或時間複雜性函式.