给定链表 0->1->2->...->n 找出链表的中点(也就是 n//2)的位置
遍历一遍(n)->计算总数->计算中点所在位置->找到中点(n//2)
slow 指针 next 一次,fast 指针 next 两次,fast 跑到头的时候,slow 指向的就是中点
(我感觉是一样的,可是很多地方都说快慢指针时间复杂度会低一点)
说一下我为什么会理解为性能一样:
代码如下:
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 的部分 (#-.-) 结帖大吉
1
jmc891205 2020-07-27 11:33:31 +08:00
说时间复杂度的话都是 O(n)
说性能的话还是快慢指针快一点 |
4
XiaoxiaoPu 2020-07-27 12:12:20 +08:00 2
@jmc891205 0.5n 错了吧
|
5
roychan 2020-07-27 12:19:28 +08:00
朴素方法空间应该用得多一点。。
|
6
raaaaaar 2020-07-27 12:27:33 +08:00 via Android
双指针是计算长度和找中点两个操作同时进行的,而遍历一次是分开的,应该双指针快
|
7
skybrown 2020-07-27 12:30:43 +08:00
实践是检验真理的唯一标准
|
8
petelin 2020-07-27 12:46:23 +08:00 via iPhone
双指针跑的指令少更快有疑问吗
|
9
jmc891205 2020-07-27 13:06:41 +08:00
|
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) 做对比的时候,就容易觉得朴素法更慢了。 |
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 次长度变量的赋值操作。 |
12
ipwx 2020-07-27 13:45:22 +08:00
流水线没有被打断,快慢法我觉得更快一点。
|
13
bruce0 2020-07-27 14:00:41 +08:00
这个有点像插入排序和冒泡排序比较了.理论上都是 O(n²) 但实际上,插入排序一般要快一点,因为插入排序需要的指令更少
|
14
wasd6267016 2020-07-27 15:19:39 +08:00
现在的算法性能分析都已经到连 int 自增都算到时间复杂度里面了吗……
|
15
yxcoder OP @wasd6267016 茴字的四种写法
|
16
wasd6267016 2020-07-27 16:11:27 +08:00
@yxcoder 有那味儿了 我觉得对大多数软工程师更有意义的是学会分析更复杂算法的时间复杂度,而不是在这比较两个 O ( n )的算法谁更快……
狗头保命 |