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 表示法（当然是在参加测试之前！），它说单循环操作，例如将元素一个一个添加到列表中，应该具有线性复杂度，或O(N)。

然而，正确的答案实际上是O(N^2)。我很困惑为什么会这样，有人能给我解释一下吗？因为我认为O(N^2)复杂性在嵌套 for循环中很常见......

4

1 回答 1

2

它是 O(n^2) 因为递归函数add有一个隐式遍历，即其中有第二个循环，如下所示：

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 回答