多項式時間の意味を説明してください
多項式時間で問題を解くことができる場合、k、c> 0を与えられた場合、サイズnの入力にアルゴリズムが取る必要があるステップは、ほとんどcn^kです。実際には、多項式の実行時間を持つアルゴリズムは、異なる入力サイズに対して最も効率的なアルゴリズムではないかもしれませんが、理論に関しては漸近的な挙動にもっと関心を持っています。その上、任意のマシンモデルで達成できる「効率」を定義することができます。