brent算法为什么比floyd算法快

2024-01-18 21:10

文章标签 算法 floyd brent

本文主要是介绍brent算法为什么比floyd算法快，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题：用一个算法，实现判断是否会出现如下的有环的单链表

在这里插入图片描述

一、floyd

以龟兔赛跑来解释这一算法，寻找单链表中是否含有一个圈。
在这里插入图片描述

一、思想：

龟和兔子同时出发，龟走一步，兔子走两步，兔子比龟快，所以兔子一定可以追上龟，就好像在环形跑道中跑的快的运动员会从后面超过跑得慢的运动员。

//头指针给龟和兔，初始化
tortoise = top
hare = topforever://兔子走两步if hare == end :return 'No Loop Found'hare = hare.nextif hare == end :return 'No Loop Found'hare = hare.next//乌龟走一步tortoise = tortoise.next//龟兔相遇则有环if hare == tortoise:return 'Loop Found'

二、时间复杂度分析：

令x是出发点到环的起点的距离，y是环的长度。乌龟最多走x+y步，兔子最多2（x+y）步。

下面给出证明：

（1）乌龟只能在环里走一圈

假设：链表的起点距离环的起点x长度，此时的乌龟在环里，距离环的起点y1长度，由题目可知，当龟兔的距离等于y时，龟兔相遇，即龟兔距离差为y。

因为兔子的速度是乌龟的两倍，所以龟兔的差距为x+y1，环的长度为y，故当乌龟走了一圈以后，龟兔之间的差距为x+y>=y。所以在乌龟还没走完一圈，就会产生一个临界点，此时的龟兔恰好相遇，也就是在某一点，x+y1* ==y。

在这里插入图片描述
（2）由1的证明结论可知，乌龟最多在环里面走一圈，所走的长度为x+y1*（y1* <y），兔子最多走2（x+y1*），y1* 表示在某一点，龟兔相遇，此时乌龟距离环的起点的距离为y1* 。

二、Brent

一、思想：

龟和兔子同时出发，龟不动，兔子走1步，第二轮，乌龟跳到兔子的位置，兔子走两步，第三轮。。。。第n轮，乌龟跳到兔子的位置，兔子走2^n步。

//初始化，兔和龟都在链表的头部turtle = toprabbit = topsteps_taken = 0 //兔子每次迭代走了几步step_limit = 2 //兔子每次迭代做多可以走几步forever://如果发现兔子到头了，结束循环if rabbit == end:return 'No Loop Found'//兔子移动一步rabbit = rabbit.nextsteps_taken += 1//兔子和乌龟相遇，则表示有环if rabbit == turtle:return 'Loop found'//兔子这个周期移动的步数到达上限if steps_taken == step_limit:steps_taken = 0 //steps_taken初始化为0step_limit *= 2 //step_limit表示下次迭代的上限翻倍// teleport the turtleturtle = rabbit //让乌龟跳到兔子的位置上

二、时间复杂度分析：

证明：brent算法中，乌龟最多在环中走一圈。

证明过程类似死于floyd的证明方式，当乌龟在环内部走了y2长度时，兔子距离乌龟为：

乌龟走了：

1+2+4…+ 2^n == x+y2

下一次兔子行走的距离为: 2^(n+1)，又

1+2+4…+ 2^n == 2^(n+1) - 1

所以龟兔距离x+y2+1

综上所述：每一轮迭代，龟走到了x+y2的地方，兔子从x+y2出发，走到2(x+y2)+1处停止，进行下一轮迭代，兔子的速度比乌龟快一倍+1，故在环中，乌龟走到x+y之前，兔子早就与其相遇，临界位置为y2* ，此时乌龟走了x+y2* ，兔子走了x+y2* +y(此时的y == x+y2*+1)。
在这里插入图片描述