algorithm算法原理证明

Floyd’s cycle-finding algorithm

Floyd’s cycle-finding algorithm是一种用于寻找链表中循环或重复元素的算法,也称为Floyd’s tortoise and hare algorithm。该算法使用两个指针,一个称为“乌龟”(tortoise)指针,另一个称为“兔子”(hare)指针。

算法的基本思路是,用两个指针同时从链表的头部出发,乌龟指针每次前进一步,兔子指针每次前进两步。如果链表中不存在循环,那么兔子指针最终会走到链表的末尾,此时算法结束。但是,如果链表中存在循环,那么兔子指针最终会进入循环中,此时兔子指针和乌龟指针必定会相遇。

当兔子指针进入循环后,它会一直绕圈,直到乌龟指针进入循环,兔子指针追上乌龟指针,也就是说,乌龟指针和兔子指针都在循环内部移动。此时,将兔子指针重新置为链表头部,再以每次前进一步的速度移动两个指针,最终它们会在循环的入口处相遇。这是因为兔子指针在每一轮循环中都比乌龟指针多走一圈,所以它们最终相遇的地方就是循环的入口。

该算法的时间复杂度为O(n),空间复杂度为O(1),其中n是链表中元素的个数。由于该算法只需要遍历链表一次,因此效率较高,被广泛应用于链表中循环或重复元素的查找。

证明过程

在使用 Floyd’s cycle-finding algorithm 检测一个数是否是合数时,如果这个数有一个非平凡因子,那么它就是合数。这是因为当一个合数 n 有一个非平凡因子 d 时,可以将 n 表示为 n=d * q 的形式,其中 q 是另一个整数。那么 n 的一个非平凡因子就是 d 或 q。如果 d=q,则 d 就是 n 的平方根,因此在检查素性时只需要检查 n 的平方根以下的整数即可。但是如果
(1)dq
那么我们可以在 Floyd’s cycle-finding algorithm 中找到一个循环,其中循环长度为偶数,这样就找到了一个非平凡的因子。

具体来说,设 f(x) 表示对 n 取模的一个函数,定义为
(2)f(x)=(x2+1)modn
从一个初始值开始,可以构造一个序列
(3)x0,x1,x2,
其中
(4)xi+1=f(xi)
x取值范围是
(5)0xi<n
因此这个序列必然存在一个循环,即存在
(6)i<jxi=xj
假设循环长度为偶数,即存在一个正整数 k,使得
(7)xi=xi+kxi+1=xi+k+1
那么可以证明
(8)d=gcd(xixi+k,n)n
证明如下:根据假设,有
(9)xi=xi+kxi+1=xi+k+1(xi+1xi)=(xi+k+1xi+k)(modn)
那么,即
(10)(xi+1xi)(xi+k+1xi+k)(modn)
由于
(11)f(x)=(x2+1)modn
因此有
(12)xi+1xi2+1(modn)

(13)xi+k+1xi+k2+1(modn)

代入上式得到
(14)xi2xi+k2xi+1xi+k+1(modn)

(15)(xixi+k)(xi+1+xi+k+11)0(modn)

(16)xi=xi+kd=gcd(xixi+k,n)=gcd(0,n)=n

因此,如果我们能够找到一个长度为偶数的环,则可以使用上述方法得到一个非平凡的因子
(17)p=gcd(2k1,n)
假设快指针和慢指针在节点 j 处相遇,此时快指针已经绕了 k 圈了,那么有:
(18)k=2
由于慢指针走过的距离是快指针的一半,即
(19)=2
因此上式可以进一步化简为:
(20)k=2
因为快指针每次走两步,所以 快指针进入环之前走过的距离 是 环的长度的整数倍,即
(21)=x
代入上式中得:
(22)k=2x1
因为 k 是整数,所以 x-1 必须是 2 的因子。根据前面的推导,环的长度是偶数,因此 x-1 必须是一个非平凡的因子,即 x-1 不等于 1和 n。因此我们可以通过找到一个非平凡的因子来判断 n 是否是合数。