仕事を頑張る人のおしりトラブル対策

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

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

よろしくおねがいします

A 回答 (2件)

演算回数は,前者が (n(n+1)/2)+n,後者が2n。


オーダは,O(n^2),後者がO(n)。
    • good
    • 0
この回答へのお礼

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

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

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

この回答への補足

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

補足日時:2008/05/23 23:40
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング