おおざっぱに言うと、n の増大に対して計算量がどの割合で膨張するのかを示すもの。 計算式の中では一番強いものに引っ張られる。↓は代表的なもの 名前 早さ 概要 数式 例 factorial time slower nのn乗に比例した時間を費やす 巡回セールスマン問題の総当た…

友人からNP完全とNP困難について分かりやすく説明してくれと言われたので、頑張ってまとめました。 時間計算量に関しては↓のエントリ参照。 時間計算量に関して-- http://d.hatena.ne.jp/nsasaki/20110426/1303807572そもそもNPって何？って話から。 Wikiped…