时间复杂度

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。

- Annita Zirki

---

@Neil：你为什么这样认为？（当然，这不是整份考试试卷的全部内容。） - ShreevatsaR

@ShreevatsaR：可能是因为大O既不是数量（“...执行了多少次？”），也不是持续时间（“...的运行时间是多少？”）。更好的做法是使用更准确的“...的时间复杂度是多少？”。 - paxdiablo

“@paxdiablo: 完全准确地说，“语句4执行的次数是O(n)”是正确的。也就是说，量/函数10n是O(n)。(完全不同的问题是，也许这篇论文应该要求Theta，或要求最小的正确O(.)，但这取决于课程的水平而可以原谅。)" - ShreevatsaR

@Neil：我不同意。教导程序员认识到他们所编写的代码的复杂性是很重要的，尽管这有些琐碎。 - Jan Hudec

@Jan：我们大致上是同意的（问题是可以的，而且隐含了什么意思，尽管更精确的表述可能会更好）。但请注意，O、Ω和Theta只是用于描述任何函数渐近增长的数学符号；它们本身与算法无关，你用它们来描述算法的运行时间是无关紧要的，而你分析最坏情况、最优情况还是平均情况也是不相关的。（参见例如这里的答案。）因此，你可以很好地使用Theta来描述平均或最坏情况复杂度。 - ShreevatsaR

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。

- paxdiablo

---

@Annita：如果这个答案对您有帮助，您可以点击旁边的勾号“接受”它。 - ShreevatsaR

该行下面的注释是错误的。大O表示的不是时间，而是渐近复杂度，通常是针对某些特定操作。在这个意义上，它更接近于“代码运行多少次”而不是任何涉及运行时间的东西（这也取决于像局部性这样的因素——大O总是假设任何给定操作都是恒定时间，而内存访问根据缓存的不同而变化很大）。 - James Kanze

@James，括号中的“用于时间复杂度”的说明清楚地表明我们在谈论时间。 - paxdiablo

@paxdiablo 除了大O表示法不能直接解决时间问题外，你无法使用大O表示法来分析时间问题。 - James Kanze

我相信对于那些确实使用它的绝大多数人来说，这是个好消息 :-) 我同意它比大多数人意识到的要复杂得多，但在这个问题的背景下，我认为我所说的是正确的。但是为了安全起见，我会删除有争议的部分，特别是因为它与问题本身没有真正的关系。 - paxdiablo

Answer 2

我不知道问题是如何被表述的，但如果措辞如你所说，你的考官并不知道大 O 的正确定义（至少在他期望“正确”的答案时）--因为 “Big O functions include smaller ”。 所以，执行为 f(n) = 10 n 的 n 函数，它是线性的，也属于 O(n)，O(n^2)，O(n log n)。如果有人要求“最小可能值”，你的答案将是：

1. 语句4会执行10n次，因此是A
2. 语句9会执行n*log n次，因此是D
3. 这里执行了两者的总和，n + n*log n ，所以D将是正确答案。

所以，如果多个答案是可行的，只要问到它被执行多少次，正确答案将是：

1. A、B、D
2. B、D
3. B、D

- flolo

---

问题2中的n log n答案是D，而不是C。 - Jan Hudec

是的，已经修复了，我在问题中误读了字母。 - flolo

我遇到的每一位导师和考官在谈论或询问某个东西的大O时，总是默认隐含着“最小正确”的大O，除非他们需要使用这个属性：如果函数是O（某个值），那么它也是O（比这个值更大的某个值）。 - Jan Hudec

@Jan Hudec：对于非正式的交谈或一些辅导，这可能还可以，但对于考试，应该要准确。定义很清楚，我遇到的所有教授在考试中都是正确和精确的，以便让每个人知道问题的意思。学生怎么知道，老师的意图不是检查他是否知道O（某物）是O（更大的某物）的子集 - 所以他所依赖的只是问题的措辞，并根据定义回答它。 - flolo

Answer 3

答案1：A，即O(n)，因为语句4将被执行10*n次。

答案2：D，即O(nlog(n))，因为语句9将被执行n*log(n)次。

答案3：D，因为总体复杂度[O(n) + O(nlog(n))]将是n*log(n)。

- bayCoder