多項式時間アルゴリズム

アルゴリズムの入力サイズが2^nで、アルゴリズムが$ O（n2^n）$時間で実行される場合。この場合、アルゴリズムは入力サイズに対して多項式時間で実行されると言えますか？多項式時間アルゴリズム

はい、これはO（k log k）時間アルゴリズムです（k = 2^n）。

2017-01-27 14:49:55

ありがとう、@デイビッドだから、多項式時間か疑似多項式だと言えるでしょうか？私はこれら2つの間で混乱しています。 –

良い質問と良い答え - すべては正しい定義に依存します。私は、行列の乗算アルゴリズムの場合、ランタイム境界は、通常、入力がサイズ「n * n」の場合には「n」という言葉で表現されると、やや困惑していました。 – Codor

@NARAYANCHANGDER多項式。擬多項式実行時間の例は、O（k^log k）である。 –

答えて