algorithm - 分析这个方法

Question

我在分析此方法时遇到问题。我试图弄清楚 Oh 的复杂性。 如果我是对的，它是 O(n^2) 因此两个 for 循环，这是算法的主导联合。但我似乎无法弄清楚如何证明这一点。

到目前为止我得到的是。

1+n*((n-1)+1)/2+n。但是当我测试它时它不可能是正确的，是吗？

文本是挪威语，如果您对理解代码有任何疑问，请大声喊出来。 (应该用英语编码，但因为我们的老师用挪威语提供所有 Material ，所以他们希望用挪威语返回。因此英语和挪威语文本: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]);
        }
    }
}

现在编辑成英文。

Answer 1

我知道 CD.genreAmount() 是 O(1) 并且您有一个固定的流派列表。对吧？

在这种情况下，您将遍历所有 CD(for i)并根据整个流派全局列表(for j)检查每一张。所以:

存在:

• N = CD 数
• M = 流派数量

订单将于O(N.M)

当然:您的算法再次迭代您的流派(在方法的末尾)，但这将是 N.M + M，当然 O(M) 总是低于 O( N.M)...所以 O(N.M+M) 等同于 O(N.M)