以下代码的总运行时间是多少（N是一个int变量）

Question

我正在备考，遇到这个问题：

下面代码的总运行时间是多少（N是一个int变量）

Z z = new Z(N);
for (int i = 0; i < N; i++) z.insert("Bob", i);

Class Z:

public class Z
{
     String[] names;
     Integer[] numbers;
     int N = 0;

     public Z(int cap)
     {
        names = new String[cap];
        numbers = new Integer[cap];
     }


     public Integer find(String S)
     {
        for (int i = 0; i < N; i++)
        {
            if (names[i].equals(S)) return numbers[i];
        }
        return null;
     }

    public void insert(String S, Integer M)
    {
        for (int i = 0; i < N; i++)
        {
            if (names[i].equals(S)) numbers[i] = M;
        }
        names[N] = S;
        numbers[N] = M;
        N++;
    }
}

我认为这个问题的答案是O(n^2)。第一个 for 循环需要 O(n) 次，方法 insert 需要 O(n) 次（注意：每次插入调用都有 n++），总计为 O(n^2)

Answer 1

首先注意主体部分的N变量和对象实例中引用的N是不一样的

创建z对象后，其私有N成员等于0，只在每次调用[=10时递增=].

所以insert方法中循环迭代的次数等于之前调用insert方法的次数

所以在 insert 方法中进行的总迭代次数（将所有 N 调用加在一起）是：

Σ_i=0..N-1 (i)

这等于：

½N(N-1)

这是 ½N² - ½N 因此 O(n²)

以下代码的总运行时间是多少（N是一个int变量）

What is the total running time of the following code (N is an int variable)

algorithm

time-complexity

cumulative-sum