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

多項式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 回答日時： 2008/05/23 21:35

演算回数は，前者が (ｎ(ｎ＋１)／２)＋ｎ，後者が２ｎ。

オーダは，Ｏ(ｎ^2)，後者がＯ(ｎ)。

この回答へのお礼

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

お礼日時：2008/05/23 23:57

No.1 回答者： Tacosan 回答日時： 2008/05/23 18:21

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

この回答への補足

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

補足日時：2008/05/23 23:40