以下代码的总运行时间是多少(N是一个int变量)
What is the total running time of the following code (N is an int variable)
我正在备考,遇到这个问题:
下面代码的总运行时间是多少(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)
首先注意主体部分的N变量和对象实例中引用的N是不一样的
创建z对象后,其私有N成员等于0,只在每次调用[=10时递增=].
所以insert
方法中循环迭代的次数等于之前调用insert
方法的次数
所以在 insert
方法中进行的总迭代次数(将所有 N 调用加在一起)是:
Σi=0..N-1 (i)
这等于:
½N(N-1)
这是 ½N² - ½N 因此 O(n²)
我正在备考,遇到这个问题:
下面代码的总运行时间是多少(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)
首先注意主体部分的N变量和对象实例中引用的N是不一样的
创建z对象后,其私有N成员等于0,只在每次调用[=10时递增=].
所以insert
方法中循环迭代的次数等于之前调用insert
方法的次数
所以在 insert
方法中进行的总迭代次数(将所有 N 调用加在一起)是:
Σi=0..N-1 (i)
这等于:
½N(N-1)
这是 ½N² - ½N 因此 O(n²)