ビッグ-Oランタイム

Question

の計算私は、次のC++の関数のためのビッグ-Oランタイムを計算すると、いくつかの指針を緊急に必要としてよ：

Fraction Polynomial::solve(const Fraction& x) const{ 
    Fraction rc; 
    auto it=poly_.begin(); 
    while(it!=poly_.end()){ 
     Term t=*it; 
     //find x^exp 
     Fraction curr(1,1); 
     for(int i=0;i<t.exponent_;i++){ 
      curr=curr*x; 
     } 
     rc+=t.coefficient_*curr; 
     it++; 
    } 
    return rc; 
} 

これはまだ私には新しい概念であるので、私は持っていますそれを正しいものにするのに少し問題があります。私は、少なくとも2つの操作が1回起こると仮定しています（auto it = poly_.begin、そして最後にrcを返します）が、whileループを使って操作数を数える方法がわかりません。私の教授によると、正しいランタイムはO（n）ではありません。もし誰かが何か指導をしてもらえれば、大いに感謝します。私はこの質問に答える方法を理解したいが、私はこの機能のようなものをオンラインで見つけることができなかったので、ここにいる。ありがとうございました。

Answer 1

になります（私たちはA_n*X^n + ... + A_0を言わせて）で与えられた点（分数として与えられるので有理値）。

最初のwhileループは、多項式のすべての個々の要素を繰り返し処理します。 n次の多項式の場合、それはn + 1の反復をもたらすので、外側のループだけがO（n）時間かかる。 しかし、多項式の各項（ランクiと言う）については、X^iの値を計算しなければならず、それは内部のforループの値です。それは線形の複雑さをもたらす線形方法を用いてX^iを計算します：O（i）。

ネストされたループが2つあるため、ループの最悪の時間複雑度を掛け合わせることで全体の複雑さが得られます。結果として生じる複雑さは、O（n）* O（n）= O（n^2）によって与えられる。 （第1項はwhileループの複雑さを示し、第2項はX^iの計算のための最悪の場合の時間複雑度を示し、O（n）はi == n）。

Answer 2

これはn次の多項式であると仮定します（最高の項はnのべき乗になります）。

外側のwhileループでは、n + 1項を繰り返します（両側に0〜nを含む）。

各項について、内側のforループでは、mを現在の項のべき乗であるm倍にします。これはn次の多項式なので、mは0からnの範囲です。平均して、乗算はn/2回行います。

全体の複雑さは、私はあなたが特定の多項式を評価するとしO（（N + 1）*（N/2））= O（N^2）