Wolfram言語

漸近関係を使ってアルゴリズムを比較する

アルゴリズムは,計算的複雑性では,大規模な入力(通常無限大と考えられる)に対する挙動によって分類される.2つのアルゴリズムは、一方のランタイムがAsymptoticLessEqual (big ),AsymptoticLess (little ),AsymptoticGreaterEqual (big ),AsymptoticGreater (little )のどれであるかによって比較される.

巡回セールスマン問題(TSP)は, 個の都市を繋いだ最短距離を求めることである.単純なアルゴリズムは 種類の経路をすべて試してみることである.HeldKarpアルゴリズムは,それを向上させておよそ ステップにしたものである.を示すとHeldKarpアルゴリズムの方が速いことがわかる.

どちらのアルゴリズムも,巡回セールスマン問題の複雑性のクラスが,時間で解ける問題のEXPTIMEほど悪くないことを示している.例えば任意の では なので,HeldKarpアルゴリズムは指数的ランタイムを持つ.

階乗関数の場合,なので線形指数では不十分である.

しかし,なので階乗関数はまだ指数的ランタイムを持つ.

近似解は の時間で見付けられるため,近似の巡回セールスマン問題は多項式時間で解ける問題である複雑性クラスPである.どの多項式アルゴリズムも指数アルゴリズムより速い.つまり

関連する例

en