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

[yxcoder]

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

朴素方法

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

快慢指针

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

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

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

[jmc891205]

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

[yxcoder]

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

[jmc891205]

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

[XiaoxiaoPu]

@jmc891205 0.5n 错了吧

[roychan]

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

[raaaaaar]

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

[skybrown]

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

[petelin]

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

[jmc891205]

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

[also24]

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

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

我们以 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]

流水线没有被打断，快慢法我觉得更快一点。

[bruce0]

这个有点像插入排序和冒泡排序比较了.理论上都是 O(n²) 但实际上,插入排序一般要快一点,因为插入排序需要的指令更少

[wasd6267016]

现在的算法性能分析都已经到连 int 自增都算到时间复杂度里面了吗……

[yxcoder]

@wasd6267016 茴字的四种写法

[wasd6267016]

@yxcoder 有那味儿了 我觉得对大多数软工程师更有意义的是学会分析更复杂算法的时间复杂度，而不是在这比较两个 O （ n ）的算法谁更快……
狗头保命