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

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

  •  
  •   OpenSSH · 2019-08-20 08:10:01 +08:00 · 2939 次点击
    这是一个创建于 1683 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如果是在同一个循环里,复杂度是 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
    tigerfyj
        1
    tigerfyj  
       2019-08-20 08:14:27 +08:00 via Android   ❤️ 1
    多做了 2000 次 a--,不算什么事吧。更多还是要考虑可读性哪种更好。
    OpenSSH
        2
    OpenSSH  
    OP
       2019-08-20 08:20:38 +08:00
    @tigerfyj #1 所以其实是一样的是吧?影响可以忽略不计。
    hauibojek
        3
    hauibojek  
       2019-08-20 08:43:54 +08:00
    不太了解算法,感觉不一样。时间复杂度和遍历次数有关
    ranleng
        4
    ranleng  
       2019-08-20 08:47:12 +08:00 via Android   ❤️ 1
    执行次数
    一个是 n
    一个是 3n

    所以时间复杂度都是 o ( n )
    (应该没说错
    passerbytiny
        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--;
    }
    ebingtel
        6
    ebingtel  
       2019-08-20 08:52:27 +08:00   ❤️ 1
    对于这个效果不太明显,换成遍历链表之类的试试
    mogami95
        7
    mogami95  
       2019-08-20 08:54:24 +08:00   ❤️ 1
    取决于伪代码 a--的实际成本
    taaaang
        8
    taaaang  
       2019-08-20 08:56:56 +08:00   ❤️ 1
    遍历本身是有开销的
    msg7086
        9
    msg7086  
       2019-08-20 08:57:19 +08:00 via Android   ❤️ 1
    复杂度是性能的增长量级描述,循环方式没有关系的。
    OpenSSH
        10
    OpenSSH  
    OP
       2019-08-20 08:57:42 +08:00
    @passerbytiny #5 请问然后呢?

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