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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1572 天前的主题，其中的信息可能已经有所发展或是发生改变。

给定链表 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 的部分 (#-.-) 结帖大吉

链表

中点

指针

slow

16 条回复 • 2020-07-27 16:11:27 +08:00

jmc891205

2020-07-27 11:33:31 +08:00

说时间复杂度的话都是 O(n)
说性能的话还是快慢指针快一点

yxcoder

2020-07-27 11:37:05 +08:00

@jmc891205 我的问题，其实我想说的是性能，我觉得他们性能是一样的

jmc891205

2020-07-27 12:09:06 +08:00

@yxcoder
朴素方法 access 了 1.5n 个结点
快慢指针只 access 了 0.5n 个

XiaoxiaoPu

2020-07-27 12:12:20 +08:00

@jmc891205 0.5n 错了吧

roychan

2020-07-27 12:19:28 +08:00

朴素方法空间应该用得多一点。。

raaaaaar

2020-07-27 12:27:33 +08:00 via Android

双指针是计算长度和找中点两个操作同时进行的，而遍历一次是分开的，应该双指针快

skybrown

2020-07-27 12:30:43 +08:00

实践是检验真理的唯一标准

petelin

2020-07-27 12:46:23 +08:00 via iPhone

双指针跑的指令少更快有疑问吗

jmc891205

2020-07-27 13:06:41 +08:00

@XiaoxiaoPu
啊好像是
其实我本意是想说循环的总迭代次数。。。

also24

2020-07-27 13:29:07 +08:00

其实快慢指针法，本质上就是朴素法变化而来的吧。

我们先来从朴素方法开始：
遍历一遍(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

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 次长度变量的赋值操作。