質問: この本をよんでアルゴリズムに関して学習しています そのp.23.に > > 定数d>0が存在して計算量がN^dの定数倍によって上から抑えられるとき、多項式時間であるといいます。 > > 注意点としては、NlogNやN√Nは多項式ではありませんが、O(NlogN)やO(N√N)は多項式時間です。 > > なぜなら、NlogN<=N^2、N√N<=N^2というように、NlogNもN√Nも多項式N^2によって上から抑えられるからです > > > とかいてありました。この部分の理解に不安や疑問があるので確認をお願いしたいです。 まず1文目は、私はこれを「計算量がN^dの定数倍未満のときは多項式時間という」と理解しましたがあっていますでしょうか? あっているとして、2^N(指数時間)とN^d(多項式時間)でグラフを描くと(N、dの値によっては。N=2、d=2など)重複する場所ができると思いますが、その重複した部分は指数時間、多項式時間のどちらと呼べばよいのでしょうか? つぎに3文目に関してですが、「NlogNもN√Nも多項式N^2によって上から抑えられる」と書かれていますが、N^2は単項式ではないのでしょうか?私はax+bのようないくつかの項の和で表せるのを多項式、x^2やaxのようなものを単項式と把握しています。これをあてはめるとN^2もNlogNもN√Nも単項式ということになるのですが・・・ つたない質問で申し訳ありませんが、ご回答よろしくお願いします
回答: いくつかポイントがあるので、分けて説明します。 ※より正確には「多項式時間」と呼ぶよりかは「多項式オーダー」とか「クラス P に属する」とか呼んだ方が良いですが、この回答では引用元に合わせて「多項式時間」と呼んでいます。 計算量の比較では関数同士を比べている 計算量の比較をするとき、我々は数学的な関数同士を比べています。たとえば N^2 と 2^N を比べているときには、関数 f(N) = N^2 と関数 g(N) = 2^N について f と g のどちらがどちらを "上から抑えている" かを考えています。このため、特定の N の値に応じて評価が変わるといったことはありません。 しかし質問者さんのおっしゃる通り、N^2 と 2^N では N が小さいときに大小関係が逆転します。つまり、2^N の方が常に N^2 より大きい訳ではありません。 実は計算量をオーダー記法で比較するときには、N を充分大きくとったときにどちらが大きいか、を比べています。より正確には、ある定数 M が存在して N >= M のとき常に f(N) < g(N) であるかどうか、を考えています。たとえば、N^2 と 2^N では N >= 5 のときは必ず N^2 < 2^N となっているため、計算量オーダーの意味で 2^N が N^2 を "上から抑えている" と考えます。 この話は参考になさっている引用部分の定義からは書き漏らされています。そうなっていたのは、おそらく分かりやすさのためです。厳密な定義は Wikipedia などに載っているので、もしご興味があればご覧ください。 単項式も多項式である これは日本の中学・高校などで習う「単項式」「多項式」の定義とはずれる場合があるのですが、大学以上で扱う数学では単項式も多項式と扱うことが一般的です。つまり、多項式とは 1 つ以上の項の和からなっている式で、単項式は 1 つだけの項からなる式である、と定義することにすれば、単項式は多項式の特別な場合である、ということになります。 この定義では N^2 は多項式であり、同時に単項式でもあります。このため単項式については今回のご質問の中では考えなくて大丈夫です。 多項式時間かどうかを考える ここまでご説明した上で、本の説明と合わせると、ある関数 f が多項式時間であるかどうかは、以下のようなステップで考えれば良いことが分かります。 1. ある正の定数 d を用意して、関数 g(N) = N^d を考える。 2. ある充分大きな定数 M を用意する。 3. ある正の定数 c を用意する。 4. N が M 以上のとき常に f(N) < c × g(N) であるならば(つまり、充分大きな N について f が g の定数倍によって上から抑えられるならば)、f は多項式時間である。 ここに出てくる色々な定数たちのことを誤魔化して、誤解を恐れずに書いても良いのであれば、「計算量がN^dの定数倍未満のときは多項式時間という」という書き方も間違いではありません。しかしより正確性を求めるのであれば、本に書いてあるような数学的な言い方を心がけることになるでしょう。