在一个循环里进行多个操作，和在多个循环里进行一个操作，在时间复杂度上，有区别吗？

[OpenSSH]

如果是在同一个循环里，复杂度是 O(n)

但是如果分开多个循环，复杂度是不是还是 O(n)？

int a = 1000;
while(a > 0) {
    // 操作 1
    // 操作 2
    // 操作 3
    a--;
}

如果把这 3 个操作，分别写在 3 个循环里，在时间复杂度上，是一样的吧？

[tigerfyj]

多做了 2000 次 a--，不算什么事吧。更多还是要考虑可读性哪种更好。

[OpenSSH]

@tigerfyj #1 所以其实是一样的是吧？影响可以忽略不计。

[hauibojek]

不太了解算法，感觉不一样。时间复杂度和遍历次数有关

[ranleng]

执行次数
一个是 n
一个是 3n

所以时间复杂度都是 o （ n ）
（应该没说错

[passerbytiny]

首先，下面两端代码是牛头不对马嘴的毫不相干的两段代码。
while(a > 0) {
// 操作 1
// 操作 2
// 操作 3
a--;
}

while(a > 0) {
// 操作 1
a--;
}
while(a > 0) {
// 操作 2
a--;
}
while(a > 0) {
// 操作 3
a--;
}

[ebingtel]

对于这个效果不太明显，换成遍历链表之类的试试

[mogami95]

取决于伪代码 a--的实际成本

[taaaang]

遍历本身是有开销的

[msg7086]

复杂度是性能的增长量级描述，循环方式没有关系的。

[OpenSSH]

@passerbytiny #5 请问然后呢？

@ebingtel #6 对，如果是链表，肯定会比数组更耗时间。

[20015jjw]

带一句可能没关系的
loop unrolling

[taogen]

算法复杂度一样，性能差距可以忽略。一定要分出胜负的话，我觉得一个循环更优，毕竟少了两个 a--操作。🐶

[Building]

没有区别。

[churchmice]

@taogen 还要考虑缓存命中率

[everydiao]

没有区别

[pkookp8]

楼主又没问效率
算法上，o(3n)等于 o(n)

[x7395759]

o(3n) = o(n)

[wdf86]

记得《深入理解计算机系统》里有一节讲的循环展开，可以参考下

[Raymon111111]

算法复杂度上讲没区别

[Aruforce]

@mogami95 #7
1K 操作 1+1k 操作 2+1k 操作 3+1Ka-- < 1K 操作 1+1k 操作 2+1k 操作 3+3Ka--
差了 2Ka-- 呢... 这还用考虑什么....

[Aruforce]

@Aruforce #20 算法时间复杂度表示 O(n ）和 O(3N) ；实际上的时间差异 才考虑 a--的性能

[mcfog]

@Aruforce 实际情况有很多的 locality 和 cache 的因素要考虑
比如说操作 123 分别是磁带机上三个不同文件的读写操作，拆三个循环就都是顺序读写，合在一起反而多了大量倒带的耗时，对比内存里的 a--完全不是一个量级的耗时

[reus]

都是 O(n)，不看常数项的

[lumotian]

考虑访问的局部性原理

[OpenSSH]

感谢各位的回复，又学到不少新知识了。

[guaohann]

我记得以前看的 csapp 里有类似例子，切换会有开销，一个循环里进行多个操作的速度更快。

[mogami95]

@mcfog 老哥说的一针见血！