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も単項式ということになるのですが・・・
つたない質問で申し訳ありませんが、ご回答よろしくお願いします