时间复杂度

Question

这个问题是为了复习过去的试卷，我只想知道我是否在正确的轨道上。

1. int i=1;
2. while (i <= n) {
3.   for (int j=1; j<10; j++)
4.     sum++;
5.   i++;
6. }
7. for( int j = 1; j <= n; j++ )
8.   for( int k = 1; k <= n; k=k*2 )
9.      sum++;

(

1.)语句4执行了多少次？

A. O(n)

B. O(n^2)

C. O(原木)

D. O(n对数)

E.上述任何一项

我在这里选择了A

(

2.)语句9执行了多少次？

A. O(n)

B. O(n^2)

C. O(原木)

D. O(n对数)

E.上述任何一项

因为第8行(k=k*2)，我选择了C

(

3.)整个代码片段的运行时间是多少？

A. O(n)

B. O(n^2)

C. O(原木)

D. O(n对数)

既然O(n)+O(logn)=O(n)，所以我选择了A。

Answer 1

您的答案1是正确的，它在一个循环中，只有n控制。

答案2不正确。如果第7行不存在，则为O(log n)，但由于第7行迫使第8和第9行多次依赖于n运行，所以答案是O(n log n)。

答案3是正确的推理，但受到事实的影响，答案2是错误的。O(n) + O(n log n)简化为O(n log n)。

所以答案是A，D和D。

Answer 2

我不知道这些问题是如何表述的，但如果你说的是这样的话，你的考官就不知道“大O”的正确定义(至少当他期待“正确”答案的时候)--因为“大O函数包括更小的”。因此，在f(n) =10n中，以n的函数形式执行的线性函数也在O( n)，O(n^2)，O(n log N)中。如果有人要求尽可能的“最小”，你的答案将是

1. 语句4被执行10 n次，所以
2. 语句9被执行n*log n次，所以D
3. 在这里执行两者之和，n+ n*log so (这里您丢失了一个*n)，所以D将是正确的。

因此，如果多个答案是可能的，并且只要求它执行了多少，那么正确的答案应该是

1. A，B，D
2. B，D
3. B，D

Answer 3

答:答。O(n)，因为语句4将执行10*n次。

Ans 2: d.O(nlog(n))，因为语句9将被执行n*log(n)次。

Ans 3: d作为总复杂度O(n) + O(nlog(n))为n*log(n)。