確定型空間複雜性測度

確定型空lei複雜性測度(deterministic spacecomplexity measure)一種複雜性測度.它是以所需空間為度量的一種複雜性測度.設M為(確定型)算法,若對M輸人字W後,計算收斂,並且在整個計算過程使用了n個空間單元(如紙帶單元),則稱n為M在輸人W的計算空間.如果計算不收斂,則其計算空間無定義.若以}M (W)表示M在輸人W時的計算空間,並以}M作為M的複雜性測度,則稱}M為空間複雜性測度,若Mo,M…為某種算法的枚舉,並以中表示從之空間複雜性測度}M,則- }}i}iE。稱為關於這種算法的空間複雜性測度確定型).空間複雜性用DSP}ICE表示.設}M為算法M的空間複雜性測度,則函式}'M<n)=max{}M<W) }W字長為n}稱為M的工作空間(函式)或稱為M的空間複雜性函式.

基本介紹

  • 中文名:確定型空間複雜性測度
  • 外文名:deterministic spacecomplexity measure

相關詞條

熱門詞條

聯絡我們