多項式時間と指数時間の違い

Question

現在、アルゴリズムの勉強をしています。
色々調べてはみたのですが、わかったようなわからないような状態で自分の理解が正しいの確認したいです。

〜わからないこと〜
多項式時間と指数時間の違い

〜現段階での理解〜
Kを定数、Nを問題の規模として考えた場合
指数時間 = K ^ N
多項式時間 = N ^ k

Nが小さい時には指数時間の方が早い
Nが大きくになるにつれて爆発的に増えて指数時間は現実的な時間ではなくなる

N、logN、NlogN、N^2、2^N、N!がある場合
指数時間 = 2^N、N!
多項式時間 = N、logN、NlogN、N^2
上記のように分類できる

このように理解しています。
これは正しいのでしょうか？
アルゴリズムの序盤の序盤なので理解を明確にしたいです。

Comments

[ps_aux_grep]

log Nは対数時間です

[youa]

指数時間と多項式時間は大枠の括りで
logNは対数時間であり多項式時間であると考えていました。
→私は多項式時間に対数時間が含まれていると考えている。
(対数時間以外にも線形時間なども多項式時間に含まれていると考えている)

上記の認識は間違いということでしょうか？
logNは対数時間で指数時間と多項式時間とは別物なのでしょうか？

[ps_aux_grep]

大枠の括りで考えるのであれば，多項式時間に入ると思います．
その話で進めるならば，定数時間も多項式時間に入ります．

[youa]

なるほど
勉強になりました。
ありがとうございました。

Answer 1

何を聞きたいかわからん。
実行時間がNの多項式(1、N、N²、N³、…の定数倍の和)で表せるものを多項式時間、
Nの指数関数で表されるものを指数時間と呼んでいるだけでは？
log NやN!は多項式でも指数でもないのでどちらにも入らない。