多項式時間 多こうしきって言われたら、 ax^m＋bx^m-1＋...+cx+d みたいなのを想像す

多項式時間

多こうしきって言われたら、
ax^m＋bx^m-1＋...+cx+d
みたいなのを想像すればいいですか？

たとえばax^2＋bx＋e^x

とか、

x＋2^x

とかなってたら意味なくないですか？笑笑

No.3 ベストアンサー 回答者： ありものがたり 回答日時： 2023/12/25 18:55

＞ 多項式時間がなにかわからないから聞いたんですけど。

それなら、そう聞けばいいのに。

「多項式時間」ってのは、アルゴリズムの実行時間が
入力データにどう依存するかを表す分類のひとつです。

何か計算を行う手順があるとして、
その計算を完了するのに要する時間が
与えるデータの量によって変わるものがあります。

例えば「整列」。
与えられた n 個の数値を小さい順に並べ直す作業に
かかる時間は、 n の値によって異なります。
データが n 個のときにかかる時間を f(n) としたとき、
n が大きくなるほど f(n) は大きくなりますが、
n の増加にともなってどのくらいのスピードで大きくなるか
は、並べ直す作業手順によって違ってきます。

その f(n) を n の関数として評価する際に、
lim[n→∞] f(n)/n^k = 0 となるような定数 k が存在する
作業手順を「多項式時間のアルゴリズム」と呼びます。

この回答へのお礼

なるほど。ありがとうございました。
高々xのべき乗で抑えられればてことか。

お礼日時：2023/12/25 23:53

No.2 回答者： kairou 回答日時： 2023/12/25 15:27

「多項式時間」が分からないなら ネットで 検索にかけてみたら。

数学の「多項式」とは 別のものでは。
私には 能力外の分野ですが。

No.1 回答者： ありものがたり 回答日時： 2023/12/25 13:56

ax^2＋bx＋e^x も、x＋2^x も、当然「x の多項式」ではないよ。

多項式って言われたら、多項式を思い浮かべればいい。
何笑ってんだか。

この回答へのお礼

多項式時間がなにかわからないから聞いたんですけど。

お礼日時：2023/12/25 14:12