2

https://www.kspub.co.jp/book/detail/5128442.html
この本をよんでアルゴリズムに関して学習しています
その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も単項式ということになるのですが・・・

つたない質問で申し訳ありませんが、ご回答よろしくお願いします

1 件の回答 1

4

いくつかポイントがあるので、分けて説明します。

※より正確には「多項式時間」と呼ぶよりかは「多項式オーダー」とか「クラス 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の定数倍未満のときは多項式時間という」という書き方も間違いではありません。しかしより正確性を求めるのであれば、本に書いてあるような数学的な言い方を心がけることになるでしょう。

3
  • ありがとうございます!ご回答いただいた内容を読みました。 恐縮ながら、その上でさらに2点質問があるのですが、「多項式とは 1 つ以上の項の和からなっている式」とすると、NlogN、N√Nが多項式ではないと書籍に書かれているのはなぜでしょうか?    また正の定数 c の幅に制限はないのでしょうか?正の定数をいくらでも大きく取れるならいつでも、f(N)<c*g(N)が成り立つように思えます。定数倍が無視できるほど大きいNを想定しているなら、定数c自体が不要になってしまうので悩んでいます。 Commented 2021年4月30日 17:19
  • 定数と変数の和と積によってのみ作られる式を多項式と定義することにすると、log 関数や平方根が入っている式は多項式とは呼べなくなります。 / c については、N を決めるより前に c を固定していることに注意してください。たとえば f(N) = N^2 と g(N) = N を f(N) と c × g(N) とで比べることを考えると、どれだけ c を大きくとったとしても、N を充分大きくとれば f(N) の方が大きくなってしまいます。この定数係数 c の必要性については、c があることによって同じくらいの増加度の関数たちをまとめるために便利という点にも触れておくと理解しやすいでしょう。たとえば f(N) = 2N と g(N) = 3N はどちらにとっても他方を定数倍によって上から抑えられるので、2N = O(3N) かつ 3N = O(2N) であると言えます。
    – nekketsuuu
    Commented 2021年4月30日 17:48
  • ご返信が遅れ申し訳ありませんでした!納得しました  おつきあい頂きありがとうございました!! Commented 2021年5月5日 9:58

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。