algorithm - 对时间复杂度的误解？

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. 登录
3. n log n
4. n2(二的幂)
5. n3(三的幂)
6. 2n(n 的幂)

Answer 1

有一次我和我的教授就同一个话题进行了一次非常有趣的讨论。我在一家非常酷的公司工作，该公司使用 beowulf 集群进行热建模。非常非常计算密集。我的教授说，如果我可以将函数从 4n^2 转换为 2n^2，我的老板会不高兴的。但如果我能把它从 4n^2 变成 4n 他会很高兴。我举手说，如果我能将时间缩短一半，我的老板会非常非常高兴。她说不，他只会对一个数量级的改进感到满意 - 相同数量级的线性改进是无关紧要的。

那天我调用我的老板。他说，如果我能将运行时间减半，他会带我飞回家，给我双倍的工资，并请我吃一年的牛排晚餐。

有时知道系数是什么很重要。其他时候则不然。所以你是绝对正确的，在处理这些代码片段的复杂性顺序时，4n 或 10000n 或 n 都是相同的 -它们是 O(n)。

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

因此，如果他说“时间复杂度是 2n”，那么他是对的。如果他说“时间复杂度是 O(2n)”，那么他是不正确的 - O(...) 意味着非常具体的东西，并且没有系数。