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

给定链表,找中点,两种方法时间复杂度对比

  •  
  •   yxcoder · 2020-07-27 11:30:31 +08:00 · 2094 次点击
    这是一个创建于 1581 天前的主题,其中的信息可能已经有所发展或是发生改变。

    给定链表 0->1->2->...->n 找出链表的中点(也就是 n//2)的位置

    朴素方法

    遍历一遍(n)->计算总数->计算中点所在位置->找到中点(n//2)
    

    快慢指针

    slow 指针 next 一次,fast 指针 next 两次,fast 跑到头的时候,slow 指向的就是中点
    

    这两种方法的时间复杂度大家觉得是怎样的?

    (我感觉是一样的,可是很多地方都说快慢指针时间复杂度会低一点)

    第 1 条附言  ·  2020-07-27 15:12:46 +08:00

    说一下我为什么会理解为性能一样:

    代码如下:

    快慢指针

    slow = fast = head
    while fast:
        slow = slow.next                                             #1
        fast = fast.next                                             #2
        if fast:
            fast = fast.next                                         #3
    return slow
    

    输入为 n,不考虑常数指令执行次数。执行次数为 3*n/2 = 1.5n

    朴素

    L = 0
    point = head
    while point:
        point = point.next                                           #1
        L+=1                                                         #2
    L //= 2
    point = head
    while L:
        point = point.next                                           #3
        L-=1                                                         #4
    return point
    

    输入为 n,不考虑常数指令执行次数。执行次数为 (1+1)*n + (1+1)*n/2 = 3n

    快慢指针性能是朴素方法的两倍

    在写朴素代码之前我一直少算了 L+=1 和 L-=1 的部分 (#-.-) 结帖大吉

    16 条回复    2020-07-27 16:11:27 +08:00
    jmc891205
        1
    jmc891205  
       2020-07-27 11:33:31 +08:00
    说时间复杂度的话都是 O(n)
    说性能的话还是快慢指针快一点
    yxcoder
        2
    yxcoder  
    OP
       2020-07-27 11:37:05 +08:00
    @jmc891205 我的问题,其实我想说的是性能,我觉得他们性能是一样的
    jmc891205
        3
    jmc891205  
       2020-07-27 12:09:06 +08:00
    @yxcoder
    朴素方法 access 了 1.5n 个结点
    快慢指针只 access 了 0.5n 个
    XiaoxiaoPu
        4
    XiaoxiaoPu  
       2020-07-27 12:12:20 +08:00   ❤️ 2
    @jmc891205 0.5n 错了吧
    roychan
        5
    roychan  
       2020-07-27 12:19:28 +08:00
    朴素方法空间应该用得多一点。。
    raaaaaar
        6
    raaaaaar  
       2020-07-27 12:27:33 +08:00 via Android
    双指针是计算长度和找中点两个操作同时进行的,而遍历一次是分开的,应该双指针快
    skybrown
        7
    skybrown  
       2020-07-27 12:30:43 +08:00
    实践是检验真理的唯一标准
    petelin
        8
    petelin  
       2020-07-27 12:46:23 +08:00 via iPhone
    双指针跑的指令少更快有疑问吗
    jmc891205
        9
    jmc891205  
       2020-07-27 13:06:41 +08:00
    @XiaoxiaoPu
    啊好像是
    其实我本意是想说循环的总迭代次数。。。
    also24
        10
    also24  
       2020-07-27 13:29:07 +08:00   ❤️ 2
    其实快慢指针法,本质上就是朴素法变化而来的吧。

    我们先来从朴素方法开始:
    遍历一遍(n)->计算总数->计算中点所在位置->找到中点(n//2)

    这里有个小问题, n/2 很容易计算,但是 n/2 对应的指针地址,该如何取出来呢?

    先来最狠的方法,我们继续从 0 开始,遍历到第 n/2 的位置,就找到对应的指针了:
    遍历一遍(n)->计算总数->计算中点所在位置->找到中点(n//2)->遍历半遍(n/2)->找到中点指针
    时间上,多跑了半遍循环,复杂度层面都是 O(n),只是常数项从 1 变成了 1.5 而已。

    然后我们用时间来换空间试试,把经过的每一个节点的指针都存进数组 arr,最后只需要取 arr[n/2] 就行了。
    时间复杂度还是 O(n) ,但是空间复杂度从 O(1) 暴增到 O(n) 了。

    然后我们想一下怎么优化,你看啊,我们其实最后只需要 arr[n/2] 这个指针,那我能不能优化成只存储 arr[n/2] 呢?
    也就是在遍历的时候,只存储 n 和 n/2 这两个节点的指针,其它的不管。
    诶?这不就是快慢指针法了么……

    快指针走了 n 步,慢指针走了 n/2 步,算下来,其实还是访问了 1.5n 个节点。
    从这个角度来说,大家的时间复杂度实际上都是 O(1.5n),空间上来说也都是 O(1) ,快慢指针法实际上还多出一个慢指针。

    但是…… 很多时候,在计算时间复杂度的时候,习惯用循环的次数来算。
    此时,由于快慢指针法的循环可以合并为 n 次甚至 n/2 次,就很容易得出快慢指针法的之间复杂度为 O(1n) 或者 O(0.5n) 的结论,再拿来和朴素法的 O(1.5n) 做对比的时候,就容易觉得朴素法更慢了。
    also24
        11
    also24  
       2020-07-27 13:38:05 +08:00
    我们以 0->1->2->3->4 这个链表为例

    朴素法的话:
    变量 - 临时变量 n,临时指针 i
    循环 - 共访问节点 8 次
    i : 0 1 2 3 4 0 1 2
    n: 1 2 3 4 5 2 1 0 ( n 先自增记录长度,再 n/2 后自减用于二次遍历)


    快慢指针法的话:
    变量 - 临时指针 fast, slow
    循环 - 共访问节点 8 次
    fast: 0 1 2 3 4
    slow: 0 1 2

    可见,朴素法多了个存长度的变量,快慢指针法多了个指针变量,但双方访问节点的数量是一致的。
    不过也可以注意到,朴素法 和 快慢指针法都 做了 8 次指针赋值操作,朴素法多了 8 次长度变量的赋值操作。
    ipwx
        12
    ipwx  
       2020-07-27 13:45:22 +08:00
    流水线没有被打断,快慢法我觉得更快一点。
    bruce0
        13
    bruce0  
       2020-07-27 14:00:41 +08:00
    这个有点像插入排序和冒泡排序比较了.理论上都是 O(n²) 但实际上,插入排序一般要快一点,因为插入排序需要的指令更少
    wasd6267016
        14
    wasd6267016  
       2020-07-27 15:19:39 +08:00
    现在的算法性能分析都已经到连 int 自增都算到时间复杂度里面了吗……
    yxcoder
        15
    yxcoder  
    OP
       2020-07-27 15:29:20 +08:00
    @wasd6267016 茴字的四种写法
    wasd6267016
        16
    wasd6267016  
       2020-07-27 16:11:27 +08:00
    @yxcoder 有那味儿了 我觉得对大多数软工程师更有意义的是学会分析更复杂算法的时间复杂度,而不是在这比较两个 O ( n )的算法谁更快……
    狗头保命
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   910 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 21:09 · PVG 05:09 · LAX 13:09 · JFK 16:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.