0

このコード セグメントに遭遇したとき、UIL のコンピューター サイエンス演習テストを行っていました (Structure<E>クラスには他にもメソッドがありましたが、問題とは関係がないようでした)。

public class Structure<E> 
{
    private E data;
    private Structure<E> s;

    Structure(E d) 
    {
        data = d; 
    }

    public void add(E d)
    {
        if (s == null)
            s = new Structure<E>(d);
        else
            s.add(d);
    }
}

// Client method
public Structure<Integer> demo(int[] vals)
{
    Structure<Integer> s;
    s = new Structure<Integer>(vals[0]);
    for (int i = 0; i < vals.length; i++)
        s.add(vals[i]);
    return s;
}

そのため、この質問では、demo()クライアント メソッドの最も制限的な複雑さを判断するよう求められました。私は大きな O 記法を読んで (もちろんテストを受ける前に!)、要素を 1 つずつリストに追加するような単一のループ操作は、線形の複雑さ、つまりO(N)を持つ必要があると述べました。

しかし、実際の正解はO(N^2)でした。どうしてなのか分からないのですが、どなたか教えていただけないでしょうか？ネストされたループではO(N^2)の複雑さが一般的だと思っていたので... for

4

1 に答える 1

2

これは O(n^2) です。これは、再帰関数addが暗黙のトラバーサル、つまり次のような 2 番目のループを持っているためです。

s = new Structure<Integer>(vals[0]);
for (int i = 0; i < vals.length; i++) {
        Structure<Integer> p = s;
        while (p.s != null) p = p.s;
        p.s = new Structure<E>(d);
 }
于 2013-03-21T04:43:37.433 に答える