时间复杂

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(log n)
D.O(n log n)
E.以上都不是

在这里我选择了A.

2.)声明9执行了多少次？
A.O(n)
B.O(n ^ 2)
C.O(log n)
D.O(n log n)
E.以上都不是

由于第8行(k = k*2),我选择了C.

3.)整个代码片段的运行时间是多少？
A. O(n)
B.O(n ^ 2)
C.O(log n)
D.O(n log n)

由于O(n)+ O(logn)= O(n)所以我选择了A.

Answer 1

你的答案1是正确的,它只在一个循环内控制n.

答案2不正确.这将是O(log n),如果第7行不存在,但是,由于7号线是迫使8,9线运行依赖于多次n,答案是O(n log n).

答案3是正确的推理,但是事实上答案2是错误的.O(n) + O(n log n)简化为O(n log n).

所以答案是A,D和D.