首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

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

  •  
  •   OpenSSH · 63 天前 · 1926 次点击
    这是一个创建于 63 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

    27 回复  |  直到 2019-08-20 23:03:58 +08:00
        1
    tigerfyj   63 天前 via Android   ♥ 1
    多做了 2000 次 a--,不算什么事吧。更多还是要考虑可读性哪种更好。
        2
    OpenSSH   63 天前
    @tigerfyj #1 所以其实是一样的是吧?影响可以忽略不计。
        3
    hauibojek   63 天前
    不太了解算法,感觉不一样。时间复杂度和遍历次数有关
        4
    ranleng   63 天前 via Android   ♥ 1
    执行次数
    一个是 n
    一个是 3n

    所以时间复杂度都是 o ( n )
    (应该没说错
        5
    passerbytiny   63 天前
    首先,下面两端代码是牛头不对马嘴的毫不相干的两段代码。
    while(a > 0) {
    // 操作 1
    // 操作 2
    // 操作 3
    a--;
    }

    while(a > 0) {
    // 操作 1
    a--;
    }
    while(a > 0) {
    // 操作 2
    a--;
    }
    while(a > 0) {
    // 操作 3
    a--;
    }
        6
    ebingtel   63 天前   ♥ 1
    对于这个效果不太明显,换成遍历链表之类的试试
        7
    mogami95   63 天前   ♥ 1
    取决于伪代码 a--的实际成本
        8
    taaaang   63 天前   ♥ 1
    遍历本身是有开销的
        9
    msg7086   63 天前 via Android   ♥ 1
    复杂度是性能的增长量级描述,循环方式没有关系的。
        10
    OpenSSH   63 天前
    @passerbytiny #5 请问然后呢?

    @ebingtel #6 对,如果是链表,肯定会比数组更耗时间。
        11
    20015jjw   63 天前 via Android   ♥ 1
    带一句可能没关系的
    loop unrolling
        12
    taogen   63 天前 via Android   ♥ 1
    算法复杂度一样,性能差距可以忽略。一定要分出胜负的话,我觉得一个循环更优,毕竟少了两个 a--操作。🐶
        13
    Building   63 天前 via iPhone   ♥ 1
    没有区别。
        14
    churchmice   63 天前 via Android   ♥ 1
    @taogen 还要考虑缓存命中率
        15
    everydiao   63 天前 via Android   ♥ 1
    没有区别
        16
    pkookp8   63 天前 via Android   ♥ 1
    楼主又没问效率
    算法上,o(3n)等于 o(n)
        17
    x7395759   63 天前   ♥ 1
    o(3n) = o(n)
        18
    wdf86   63 天前   ♥ 1
    记得《深入理解计算机系统》里有一节讲的循环展开,可以参考下
        19
    Raymon111111   63 天前   ♥ 1
    算法复杂度上讲没区别
        20
    Aruforce   63 天前   ♥ 1
    @mogami95 #7
    1K 操作 1+1k 操作 2+1k 操作 3+1Ka-- < 1K 操作 1+1k 操作 2+1k 操作 3+3Ka--
    差了 2Ka-- 呢... 这还用考虑什么....
        21
    Aruforce   63 天前
    @Aruforce #20 算法时间复杂度表示 O(n )和 O(3N) ;实际上的时间差异 才考虑 a--的性能
        22
    mcfog   63 天前 via Android   ♥ 2
    @Aruforce 实际情况有很多的 locality 和 cache 的因素要考虑
    比如说操作 123 分别是磁带机上三个不同文件的读写操作,拆三个循环就都是顺序读写,合在一起反而多了大量倒带的耗时,对比内存里的 a--完全不是一个量级的耗时
        23
    reus   63 天前   ♥ 1
    都是 O(n),不看常数项的
        24
    lumotian   63 天前   ♥ 1
    考虑访问的局部性原理
        25
    OpenSSH   63 天前
    感谢各位的回复,又学到不少新知识了。
        26
    guaohann   63 天前 via Android
    我记得以前看的 csapp 里有类似例子,切换会有开销,一个循环里进行多个操作的速度更快。
        27
    mogami95   62 天前
    @mcfog 老哥说的一针见血!
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2809 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 27ms · UTC 12:18 · PVG 20:18 · LAX 05:18 · JFK 08:18
    ♥ Do have faith in what you're doing.