next up previous
: 問題(1),(2)対する多項式時間アルゴリズムの存在性 : 計算時間の比較(多項式=良い,指数関数=悪い) : 計算時間の比較(多項式=良い,指数関数=悪い)

計算時間の比較(多項式=良い,指数関数=悪い)

ある問題Pを解く2つのアルゴリズムA, Bがある. Aは n6時間, Bは2n時間かかる. ここでnは入力のサイズで, 例えば最大クリーク問題ならばグラフの頂点数, 最大充足割当問題ならば変数の個数である. nが30未満の場合アルゴリズムBの方が計算時間は早いが, 30を超えるとAの方が早くなる. さらに50を超えるとBの計算時間はAの計算時間の1万倍を超える値となる. この理由は, n6はnに関する多項式なのでnが増えても 急激には値が増加しないが, 2nは指数関数なので 急激に増加する. 従って, できれば計算時間を表す関数が, 指数関数ではなく多項式となるような アルゴリズムを設計したい. 計算時間を表す関数が多項式なアルゴリズムを, 多項式時間アルゴリズム と呼ぶ.

Koichi Yamazaki 平成12年3月15日