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 的平方根以下的整数即可。但是如果
那么我们可以在 Floyd’s cycle-finding algorithm 中找到一个循环,其中循环长度为偶数,这样就找到了一个非平凡的因子。
具体来说,设 f(x) 表示对 n 取模的一个函数,定义为
从一个初始值开始,可以构造一个序列
其中
x取值范围是
因此这个序列必然存在一个循环,即存在
假设循环长度为偶数,即存在一个正整数 k,使得
那么可以证明
证明如下:根据假设,有
那么,即
由于
因此有
代入上式得到
即
因此,如果我们能够找到一个长度为偶数的环,则可以使用上述方法得到一个非平凡的因子
假设快指针和慢指针在节点 j 处相遇,此时快指针已经绕了 k 圈了,那么有:
由于慢指针走过的距离是快指针的一半,即
因此上式可以进一步化简为:
因为快指针每次走两步,所以 快指针进入环之前走过的距离 是 环的长度的整数倍,即
代入上式中得:
因为 k 是整数,所以 x-1 必须是 2 的因子。根据前面的推导,环的长度是偶数,因此 x-1 必须是一个非平凡的因子,即 x-1 不等于 1和 n。因此我们可以通过找到一个非平凡的因子来判断 n 是否是合数。