对时间复杂性的误解？

Question

我的问题

我目前正在学习时间复杂性，并向我介绍了解决时间复杂性的以下示例：

sum=0
for j=1 to 12
    add = add + figures[j]
average = add/12
print average

for x=12 to n-1{
 total = total - figures[x-11] + figures[x+1]
 average=total/12
 print average 
}

我的回答是:时间复杂性=n解释/思考过程:第一个循环执行12次，第二个循环执行n-12次。我相信时间复杂度是'n‘，因为n-12+12=n，并且循环不是嵌套的。

老师的回答:时间复杂性= 2n我不知道为什么。任何帮助在理解将是伟大的！

此外，是否有一种方法来帮助实现其他共同的复杂性？

例如：

1. N
2. 原木n
3. N对数n
4. n2 (功率为2)
5. n3 (功率为3)
6. 2n (功率到n)

Answer 1

是的，他的回答是正确的。时间复杂度为2n。

在这个示例中，for循环将运行某个值n。无论它是从1到12还是从1到1000，都不重要，因为无论这个值n是什么，for循环一旦达到其极限n，就会结束执行。

在他的回答中，时间复杂度= 2n来自于这样一个事实:对于这个示例，将执行两个for循环。

看看这个文章。它提供了一些直截了当的解释

Answer 2

有一次，我和我的教授就这个话题进行了一次非常有趣的讨论。我曾为一家非常酷的公司工作，该公司用贝奥武夫星系团进行热建模。非常非常需要计算。我的教授说，如果我能把一个函数从4n^2拿到2n^2，我的老板就不会高兴了。但如果我能把它从4n^2带到4n，他会很高兴的。我举起手说，如果我能把时间减少一半，我的老板会非常非常高兴的。她说不，他只会对数量级的改进感到满意--同样数量级的线性改进是无关紧要的。

那天我给我老板打了电话。他说，如果我能把运行时间减少一半，他会送我回家，给我双倍的工资，给我买一年的牛排晚餐。

有时候，知道系数是什么很重要。因此，在处理这些代码段的复杂性顺序时，4n、10000n或n都是相同的--它们是O(n)。

顺便说一下，他可能使用2n而不是n，因为第二个循环中有两个查找，而第一个循环(运行一定次数)只有一个查找。

所以，如果他说“时间复杂性是2n的”，他是正确的。如果他说“时间复杂性是O(2n)”，他是错误的-O(.)意思是非常具体的东西，而且没有系数。