如果是在同一个循环里，复杂度是 O(n)
但是如果分开多个循环，复杂度是不是还是 O(n)？
int a = 1000;
while(a > 0) {
// 操作 1
// 操作 2
// 操作 3
a--;
}
如果把这 3 个操作，分别写在 3 个循环里，在时间复杂度上，是一样的吧？
This topic created in 2638 days ago, the information mentioned may be changed or developed.
 |
1
多做了 2000 次 a--，不算什么事吧。更多还是要考虑可读性哪种更好。
|
1 |
hauibojekAug 20, 2019
3
不太了解算法，感觉不一样。时间复杂度和遍历次数有关
|
 |
4
执行次数
一个是 n 一个是 3n 所以时间复杂度都是 o （ n ） （应该没说错 |
 |
passerbytinyAug 20, 2019
5
首先，下面两端代码是牛头不对马嘴的毫不相干的两段代码。
while(a > 0) { // 操作 1 // 操作 2 // 操作 3 a--; } while(a > 0) { // 操作 1 a--; } while(a > 0) { // 操作 2 a--; } while(a > 0) { // 操作 3 a--; } |
 |
6
对于这个效果不太明显，换成遍历链表之类的试试
|
 |
7
取决于伪代码 a--的实际成本
|
 |
8
遍历本身是有开销的
|
 |
9
复杂度是性能的增长量级描述，循环方式没有关系的。
|
 |
10
|
 |
11
带一句可能没关系的
loop unrolling |
 |
12
算法复杂度一样，性能差距可以忽略。一定要分出胜负的话，我觉得一个循环更优，毕竟少了两个 a--操作。🐶
|
 |
13
没有区别。
|
 |
14
@taogen 还要考虑缓存命中率
|
 |
15
没有区别
|
 |
16
楼主又没问效率
算法上，o(3n)等于 o(n) |
 |
17
o(3n) = o(n)
|
 |
18
记得《深入理解计算机系统》里有一节讲的循环展开，可以参考下
|
 |
19
算法复杂度上讲没区别
|
 |
20
@mogami95 #7
1K 操作 1+1k 操作 2+1k 操作 3+1Ka-- < 1K 操作 1+1k 操作 2+1k 操作 3+3Ka-- 差了 2Ka-- 呢... 这还用考虑什么.... |
 |
22
@Aruforce 实际情况有很多的 locality 和 cache 的因素要考虑
比如说操作 123 分别是磁带机上三个不同文件的读写操作，拆三个循环就都是顺序读写，合在一起反而多了大量倒带的耗时，对比内存里的 a--完全不是一个量级的耗时 |
 |
23
都是 O(n)，不看常数项的
|
 |
24
考虑访问的局部性原理
|
|
25
感谢各位的回复，又学到不少新知识了。
|
 |
guaohannAug 20, 2019 via Android
26
我记得以前看的 csapp 里有类似例子，切换会有开销，一个循环里进行多个操作的速度更快。
|
Select Language