这是一个创建于 1929 天前的主题，其中的信息可能已经有所发展或是发生改变。
如果是在同一个循环里，复杂度是 O(n)
但是如果分开多个循环，复杂度是不是还是 O(n)？
int a = 1000;
while(a > 0) {
// 操作 1
// 操作 2
// 操作 3
a--;
}
如果把这 3 个操作，分别写在 3 个循环里，在时间复杂度上，是一样的吧？
 |
1
tigerfyj 2019-08-20 08:14:27 +08:00 via Android  1
多做了 2000 次 a--，不算什么事吧。更多还是要考虑可读性哪种更好。
|
 |
3
hauibojek 2019-08-20 08:43:54 +08:00
不太了解算法，感觉不一样。时间复杂度和遍历次数有关
|
 |
4
ranleng 2019-08-20 08:47:12 +08:00 via Android 1
执行次数
一个是 n 一个是 3n 所以时间复杂度都是 o （ n ） （应该没说错 |
 |
5
passerbytiny 2019-08-20 08:47:31 +08:00
首先，下面两端代码是牛头不对马嘴的毫不相干的两段代码。
while(a > 0) { // 操作 1 // 操作 2 // 操作 3 a--; } while(a > 0) { // 操作 1 a--; } while(a > 0) { // 操作 2 a--; } while(a > 0) { // 操作 3 a--; } |
 |
6
ebingtel 2019-08-20 08:52:27 +08:00 1
对于这个效果不太明显，换成遍历链表之类的试试
|
 |
7
mogami95 2019-08-20 08:54:24 +08:00 1
取决于伪代码 a--的实际成本
|
 |
8
taaaang 2019-08-20 08:56:56 +08:00 1
遍历本身是有开销的
|
 |
9
msg7086 2019-08-20 08:57:19 +08:00 via Android 1
复杂度是性能的增长量级描述，循环方式没有关系的。
|
 |
10
OpenSSH OP |
 |
11
20015jjw 2019-08-20 09:00:14 +08:00 via Android 1
带一句可能没关系的
loop unrolling |
 |
12
taogen 2019-08-20 09:07:09 +08:00 via Android 1
算法复杂度一样，性能差距可以忽略。一定要分出胜负的话，我觉得一个循环更优，毕竟少了两个 a--操作。🐶
|
 |
13
Building 2019-08-20 09:13:38 +08:00 via iPhone 1
没有区别。
|
 |
14
churchmice 2019-08-20 09:24:01 +08:00 via Android 1
@taogen 还要考虑缓存命中率
|
 |
15
everydiao 2019-08-20 09:25:01 +08:00 via Android 1
没有区别
|
 |
16
pkookp8 2019-08-20 09:27:39 +08:00 via Android 1
楼主又没问效率
算法上，o(3n)等于 o(n) |
 |
17
x7395759 2019-08-20 09:40:09 +08:00 1
o(3n) = o(n)
|
 |
18
wdf86 2019-08-20 09:56:47 +08:00 1
记得《深入理解计算机系统》里有一节讲的循环展开，可以参考下
|
 |
19
Raymon111111 2019-08-20 09:59:06 +08:00 1
算法复杂度上讲没区别
|
 |
20
Aruforce 2019-08-20 11:05:03 +08:00 1
@mogami95 #7
1K 操作 1+1k 操作 2+1k 操作 3+1Ka-- < 1K 操作 1+1k 操作 2+1k 操作 3+3Ka-- 差了 2Ka-- 呢... 这还用考虑什么.... |
 |
22
mcfog 2019-08-20 11:14:39 +08:00 via Android 2
@Aruforce 实际情况有很多的 locality 和 cache 的因素要考虑
比如说操作 123 分别是磁带机上三个不同文件的读写操作，拆三个循环就都是顺序读写，合在一起反而多了大量倒带的耗时，对比内存里的 a--完全不是一个量级的耗时 |
 |
23
reus 2019-08-20 11:23:21 +08:00 1
都是 O(n)，不看常数项的
|
 |
24
lumotian 2019-08-20 12:38:25 +08:00 1
考虑访问的局部性原理
|
|
25
OpenSSH OP 感谢各位的回复，又学到不少新知识了。
|
 |
26
guaohann 2019-08-20 19:18:44 +08:00 via Android
我记得以前看的 csapp 里有类似例子，切换会有开销，一个循环里进行多个操作的速度更快。
|
Select Language