会社のブログログイン登録スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。1,744件2https://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の値によっては。どちらと呼べばよいのでしょうか?つぎに3文目に関してですが、「NlogNもN√Nも多項式N^2によって上から抑えられる」と書かれていますが、N^2は単項式ではないのでしょうか?私はax+bのようないくつかの項の和で表せるのを多項式、x^2やaxのようなものを単項式と把握しています。(投稿順)4いくつかポイントがあるので、分けて説明します。属する」とか呼んだ方が良いですが、この回答では引用元に合わせて「多項式時間」と呼んでいます。計算量の比較では関数同士を比べている計算量の比較をするとき、我々は数学的な関数同士を比べています。値に応じて評価が変わるといったことはありません。小さいときに大小関係が逆転します。大きい訳ではありません。大きくとったときにどちらが大きいか、を比べています。あるかどうか、を考えています。この話は参考になさっている引用部分の定義からは書き漏らされています。なっていたのは、おそらく分かりやすさのためです。載っているので、もしご興味があればご覧ください。定義とはずれる場合があるのですが、大学以上で扱う数学では単項式も多項式と扱うことが一般的です。項からなる式である、と定義することにすれば、単項式は多項式の特別な場合である、ということになります。多項式であり、同時に単項式でもあります。このため単項式については今回のご質問の中では考えなくて大丈夫です。多項式時間であるかどうかは、以下のようなステップで考えれば良いことが分かります。