分析此方法

我在分析此方法時遇到問題。我試圖找出大哦複雜性。如果我是對的，它是O（n^2），因此兩個for循環，這是算法的主要關節。但我似乎無法弄清楚如何證明它。分析此方法

我得到這個東西的東西是。

1 + n *（（n-1）+1）/ 2 + n。但是，當我測試這個它不能是正確的，可以嗎？

文字在挪威語中，如果您在理解代碼方面有任何問題只是大喊大叫。（必須用英文代碼，但因爲我們的老師正在給所有的材料在挪威，他們想回去挪威因此，英國和挪威的文本：P）

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]); 
     } 
    } 
}

現在編輯爲英語。

來源

2012-02-08 Destidom

'antall'定義在哪裏？而且，如果它不同於'CD.sjangerAnt（）'，那麼它不會是'O（n^2）'，而是'O（m * n）'。 – 2012-02-08 16:39:21

由於CD.sjangerAnt是一種方法，它大概不是恆定的。根據Cd.sjangerAnt，此方法可以從O（n）到O（無窮遠）的任何位置。 – emory 2012-02-08 16:49:11

啊，這就對了。那麼該方法是O（m * n）。（謝謝！）方法CD.sjangerAnt（）只是一個簡單的返回方法，具有O（1）。但我的主要問題是如何證明它是數學的。 – Destidom 2012-02-08 16:57:48

據我所知，CD.genreAmount（）是O（1），你有一個固定的流派列表。對？

在這種情況下，您將遍歷所有CD（for i）並檢查每個CD與您的整個流派全局列表（for j）。所以：

是：

N = CD計數
M =類型計數

順序將由O(N.M)

當然：你的算法遍歷你流派再次（在方法結束時），但這將是N.M + M，當然O（M）總是低於O（NM）...所以O(N.M+M)是相當於O(N.M)

來源

2012-02-08 17:04:52 helios

是的，沒錯！非常感謝你的幫助！ – Destidom 2012-02-08 17:16:00

回答

相關問題