このメソッドを分析する

Question

このメソッドを解析する際に問題があります。 Imは大きなああ複雑さを把握しようとしています。 もし私が正しいのであれば、それはO（n^2）なので、アルゴリズムの支配的なジョイントである2つのforループです。しかし、私はそれを証明する方法を把握していないようです。

これまでに得たものがあります。

1 + n *（（n-1）+1）/ 2 + n。しかし、私はこれを試すとき、それは正しいことができない、できますか？

テキストはノルウェー語で、コードを理解することに問題がある場合は、ただ叫ぶだけです。

public void skrivUtStat(){ 
    LinearNode<CD> temp = start; 
    int[] amt = new int[CD.GenreAmt()]; 
    String[] genre = CD.sendGenre(); 

    if(amount != 0){ 
     for(int i=0; i<amount; i++){ 
      for(int j=0; j<CD.genreAmount(); j++){ 
       if(temp.getElement().getGenreNr() == j){ 
        ant[j] += 1; 
       } 
      } // End inner for-loop 
      temp = temp.GetNext();        // O(1) 
     }// End outer for-loop 

     for(int a=0; a<CD.GenreAmt(); a++){ 
      System.out.println(Genre[a] + ":"); 
      System.out.println(ant[a]); 
     } 
    } 
} 

英語に今すぐ編集： は（P英語でコーディングする必要がありますが、私たち教師がノルウェー語ですべての材料を与えているので、彼らは戻っノルウェーしたがって、英語とノルウェーのテキストでそれをしたいです。）。

Answer 1

CD.genreAmount（）はO（1）であり、ジャンルの固定リストがあることを理解しています。右？

この場合、すべてのCD（for i）を繰り返し処理し、ジャンル全体のグローバルリスト（for j）に対してそれぞれを確認しています。だから、：

ビーイング：あなたのアルゴリズムは再びあなたのジャンルを反復処理されます。

• N = CD・カウント
• M =ジャンル

注文はもちろんO(N.M)

によりだろう数えます（メソッドの最後に）、それはN.M + Mとなります。もちろん、O（M）は常にO（NM）よりも低くなります。だからO(N.M+M)はと同等ですO(N.M)