时间复杂度

这个问题是修订的目的从过去的考卷我只是想知道如果我在正确的轨道时间复杂度

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

来源

2011-05-23 Annita Zirki

@尼尔：你为什么这么认为？（当然，这不是完整的考卷。） – ShreevatsaR 2011-05-23 07:22:47

@ShreevatsaR：可能是因为大O既不是数量（“多少次......”），也不是持续时间（“什么是运行时间......“）。更好的是更准确的“什么是...的时间复杂度？”。 – paxdiablo 2011-05-23 07:24:48

@paxdiablo：说“语句4被执行的次数是O（n）”是完全准确的。即，量/函数10n是O（n）。（一个完全不同的问题是，纸可能要求Theta，或要求最小的正确的O（。），但这是可以原谅的，取决于课程的级别。） – ShreevatsaR 2011-05-23 07:27:00

你的回答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。

来源

2011-05-23 07:09:45 paxdiablo

@Annita：如果这个答案对你有帮助，你可以通过点击旁边的勾号来“接受”它。 – ShreevatsaR 2011-05-23 07:34:59

该行下的评论是错误的。大O不说时间;它指定了渐近复杂度，通常用一些特定的操作来表示。从这个意义上说，它更接近于“一段代码运行多少次”，而不是涉及到运行时的任何事情（这也取决于诸如局部性之类的事情---大-O总是假定任何给定操作是恒定时间的，其中因为内存访问因缓存而异）。 – 2011-05-23 09:16:01

@詹姆斯，“时间复杂度”的括号表示清楚表明我们在这里谈论时间。 – paxdiablo 2011-05-23 15:58:02

我不知道如何制定问题，但如果措辞就像你说的那样，考官并不知道大O的正确定义（至少在他期待“正确”的答案时） - 作为“大O函数包括更小的“。因此，在f（n）= 10 n中线性的函数n也是在O（n），O（n^2），O（n log n）中执行的。如果有人问，对于 “最小” 可能的话，你的答案会是

声明4执行10 N倍，所以A
声明9执行的n * log n次，所以d
这里它执行两者的总和，n + n * log n所以（这里你失去了一个* n），所以D就是正确的。

所以，如果可以有多种答案，它只是要求它有多少执行，正确的答案是

A，B，d
B，d
乙，D

来源

2011-05-23 07:18:45 flolo

问题2中的* n * log * n *答案是D，而不是C. – 2011-05-23 07:23:20

是的，已经修复它，误解了问题中的字母。 – flolo 2011-05-23 07:25:05

我遇到的每个导师和考官总是含蓄地指*最小的正确*大O当他们谈论/询问关于某事物的大O时，除非他们需要使用属性，如果函数是O（某物）而不是它也是O（更大的东西）。 – 2011-05-23 07:42:41

答案1：A ie。 O（n）作为陈述4将被执行10 * n次。

答案2：D ie。 O（nlog（n））作为语句9将执行n * log（n）次。答案3：作为总体复杂度[O（n）+ O（nlog（n））]的D将是n * log（n）。

来源

2011-05-23 08:34:20 bayCoder

回答

相关问题