アルゴリズムの計算量とオーダ

質問

多項式P(x) = (AnX＾n)+(An-1X＾n-1)+…A1X+A0と、この式を変形した
P(x) = (…((AnX+An-1)X+An-2)X+…+A1)X+A0を、式どおりに計算すると各々の演算回数はどうなるでしょうか？
(Aの横のnや１などの数字は配列番号です)

また、これらの結果をオーダ表記で表す場合どのように考えれば良いでしょうか？

よろしくおねがいします

回答No.2

jjon-com · ベストアンサー

演算回数は，前者が (ｎ(ｎ＋１)／２)＋ｎ，後者が２ｎ。
オーダは，Ｏ(ｎ^2)，後者がＯ(ｎ)。

お礼

ご回答頂きありがとうございます
変形前と変形後の多項式では結果がここまで変わるものなんですね。

回答No.1

Tacosan

「演算回数」の定義にもよるはずですが, あなたはどうなると思いますか?

補足

ご回答頂きありがとうございます
実のところアルゴリズムはまだ習ったばかりでよくわかってないのです…
「演算回数」というのは恐らく時間計算量のことだと思います。