UVA 11549 Calculator Conundrum Floyd判圈算法 Brent判圈算法 相关性质及证明

UVA 11549 Calculator Conundrum Floyd判圈算法 Brent判圈算法 相关性质及证明

题目地址

.php?option=onlinejudge&page=show_problem&problem=2544

题意

判定一个循环节中最大的数是多少

分析

首先，题目中的数据范围太大，不能用vis数组来存下访问过的数，一个方法是可以使用set，不过set会带来 O(logn) $O(logn)$的额外复杂度，由于题目中没有让我们存在下所有出现的数，只是记录出现最大的数，所以有没有时间复杂度 O(n) $O(n)$以及空间复杂度 O(1) $O(1)$的算法呢？
大家都清楚的应该就是Floyd判圈算法了，网上也有相应性质的证明，但是比Floyd更快的Brent算法网上好像没有相关的中文介绍，所以这里打算基于自己的理解介绍下这两种算法。

Floyd判圈算法

让兔子每个单位时间前进2步，乌龟每个单位时间前进1步，在 O(n)