計算量 : プログラミング
計算量のメモ。
多項式時間と指数時間
あるnサイズの問題を解くのに必要な計算量には大きく多項式時間と指数時間がある。
nが大きくなると指数時間は爆発的に大きくなる[1]。
簡単な例を挙げる。
多項式: n2 102 = 100, 202 = 400 4倍
指数 : 2n 210 = 1024, 220 = 1048576 1024倍
またnlogn ≤ n2
logの底は2とする。
nlogn ≤ n2 ≤ 2n
n = 3は除く
1. 多項式時間の多項式にはn乗を含めない。anは指数時間になる。
コメント
No comments yet.
コメントの投稿
改行と段落タグは自動で挿入されます。
メールアドレスは表示されません。