多項式時間
問題の要素数Nに対して処理数の最悪回数をNの多項式で表すことができる問題を「多項式時間のアルゴリズム」という。
一般的に多項式時間で解ける問題は簡単に解ける問題とされ、多項式時間より早いスピードで計算時間がNに対して増加する問題は、難しい問題とされる。$ O(N!) $ O(2^N)など。
わかりやすくするために、「簡単に解ける」という言葉を用いられることが多い。
多項式時間で解けるからといって必ずしも簡単に解ける問題とは限らない。$ O(N^{10^{100}})が現実的な時間で解けるか？ということ。