時間計算量クラス

書きかけ
計算可能性と実際に計算して答えを求める努力をすることとは同じではない。「いつかは終わるかもしれないけれど、あまりに時間がかかりすぎる方法」は、はなから始めない方がよい。この『かかる時間の予想』を数値化したもの。入力情報量によって計算量は表現される

• オーダ記法とか
• と
  • 計算ステップが多項式(Polynoimal)に表される((Polynomial)は、よりおおいにまし)
  • ,ともに多項式時間決定性だが、前者は、決定性アルゴリズム、後者は非決定性アルゴリズムである点が異なる。
• と
  • <=<=
    • この不等号の意味が、すでに算数の正解の不等号と同じではないのだが、『意味合い』として、難しさの序列がこう、という意味
  • Mathematicaの数学関連用語サイトの説明が一番わかりやすいと思う。
    • NP-hardの説明
    • NP-completeの説明
  • "X-hard(X-困難)","X-complete(X-完全)"とは
    • いずれも、"X"と呼ばれる諸問題の中でも難しい問題に属する点では同じ。ただし、"X-hard"は、『"X-hard"を解くアルゴリズムは、他の"X"の問題に("NP-hard","NP-complete"の場合には、polynomialに)使いまわしてあげることができることからわかるように、すべての"X"問題と比べて、いつもそれ以上に難しい。ただし、"X-hard"自身が"X"であることが保証されている必要はない』。"X-complete"は『"X-hard"で、かつ自身も"X"であることからわかるように、Xの中でもっとも難しい』