遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

時間計算量と領域計算量

アルゴリズム Glossary

時間計算量はステップ数、領域計算量は情報の保持量(メモリ負荷)

  • 実際の実行にあたってはそれぞれの計算量により制約があり、アルゴリズムは、それらの負荷により分類される
  • 計算量も『決定的(Deterministic)』か『非決定的(Non-deterministic)』かで２分される
    • L : 領域負荷で \log nにて決定的な計算量
    • NL : 領域負荷で \log nにて非決定的な計算量
    • PSPACE : 領域負荷で \Large n^iにて決定的な計算量
    • E : 時間負荷で \Large i^nにて決定的な計算量
    • NE : 時間負荷で \Large i^nにて非決定的な計算量
    • EXP : 時間負荷で \Large 2^{n^i}にて決定的な計算量
    • NEXP : 時間負荷で \Large 2^{n^i}にて非決定的な計算量