每日算法 — 使用java实现Brent判圈算法：Floyd判圈的步长优化与最小周期检测

算法概述

Brent判圈算法（Brent’s Cycle Detection Algorithm）由Richard P. Brent于1980年提出，是检测迭代序列中循环（cycle）的高效算法。与经典的Floyd龟兔赛跑算法相比，Brent算法使用不同的步长策略：龟（tortoise）保持不动，兔（hare）以2的幂次步长跳跃，每次跳跃后检查是否与龟相遇。这种策略在平均情况下比Floyd算法减少约30%的函数求值次数，是判圈算法中实际运行效率最高的方案之一。该算法广泛应用于伪随机数质量检测、密码学分析、链表环检测和Pollard-Rho因数分解等领域。

核心思想

Brent算法的核心创新在于步长控制策略：

1. 初始化：龟位于起点x₀，兔也位于起点x₀，当前步长上限power=1，步长计数steps=0。

2. 跳跃阶段：兔每次前进一步（x = f(x)），steps计数增加。每走power步后，将龟移动到兔的位置，power翻倍，steps归零。

3. 检测阶段：在每次跳跃过程中，比较兔和龟的位置。如果相遇，则发现循环。

4. 周期确定：首次相遇时，兔走过的总步数即为循环的周期λ（lambda）。

5. 起点确定：将一个指针放回起点，两个指针同步前进，再次相遇的位置即为循环起点μ（mu）。

数学原理

设迭代函数为f，序列定义为xᵢ₊₁ = f(xᵢ)。若序列进入循环，则存在最小的μ（循环起点）和λ（循环周期），使得对于所有i≥μ，有xᵢ = xᵢ₊λ。

Brent算法的正确性基于以下观察：当兔以递增的步长上限前进时，必然存在某个power值使得power ≥ λ且兔在两次龟移动之间完成至少一圈循环，从而保证相遇检测不会遗漏任何循环。

Java实现

import java.util.function.Function;

/**
 * Brent判圈算法实现
 * 用于检测迭代序列中的循环，并计算循环起点和周期
 */
public class BrentCycleDetection {

    /**
     * 判圈结果封装类
     */
    public static class CycleResult {
        public final boolean hasCycle;      // 是否存在循环
        public final int mu;                // 循环起点（从0开始计数）
        public final int lambda;            // 循环周期
        public final long meetingPoint;     // 相遇点的值

        public CycleResult(boolean hasCycle, int mu, int lambda, long meetingPoint) {
            this.hasCycle = hasCycle;
            this.mu = mu;
            this.lambda = lambda;
            this.meetingPoint = meetingPoint;
        }

        @Override
        public String toString() {
            if (!hasCycle) {
                return "CycleResult{无循环}";
            }
            return String.format(
                "CycleResult{循环起点μ=%d, 周期λ=%d, 相遇点=%d}",
                mu, lambda, meetingPoint
            );
        }
    }

    /**
     * Brent判圈算法核心实现
     * @param f 迭代函数
     * @param x0 起始值
     * @return 判圈结果
     */
    public static CycleResult detectCycle(Function<Long, Long> f, long x0) {
        // 阶段一：检测循环并计算周期λ
        long tortoise = x0;           // 龟保持在固定位置
        long hare = f.apply(x0);      // 兔前进一步
        int power = 1;                // 当前步长上限
        int lambda = 1;               // 周期计数

        while (tortoise != hare) {
            // 如果兔走了power步还没遇到龟，则将龟移到兔的位置，power翻倍
            if (power == lambda) {
                tortoise = hare;
                power *= 2;
                lambda = 0;
            }
            hare = f.apply(hare);
            lambda++;

            // 安全检查：防止非循环序列无限循环
            if (lambda > 1_000_000) {
                return new CycleResult(false, -1, -1, -1);
            }
        }

        // 阶段二：确定循环起点μ
        // 将一个指针放回起点，另一个保持在相遇点
        long ptr1 = x0;
        long ptr2 = hare;
        int mu = 0;

        while (ptr1 != ptr2) {
            ptr1 = f.apply(ptr1);
            ptr2 = f.apply(ptr2);
            mu++;
        }

        return new CycleResult(true, mu, lambda, hare);
    }

    /**
     * 链表版本的判圈算法
     * 检测链表是否存在环，并返回环的入口节点
     */
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    /**
     * 使用Brent算法检测链表环
     * @param head 链表头节点
     * @return 环的入口节点，若无环返回null
     */
    public static ListNode detectLinkedListCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode tortoise = head;
        ListNode hare = head.next;
        int power = 1;
        int steps = 1;

        // 阶段一：寻找相遇点
        while (hare != null && hare != tortoise) {
            if (steps == power) {
                tortoise = hare;
                power *= 2;
                steps = 0;
            }
            hare = hare.next;
            steps++;
        }

        if (hare == null) {
            return null;  // 无环
        }

        // 阶段二：确定环入口
        // 计算周期lambda
        int lambda = 1;
        hare = tortoise.next;
        while (hare != tortoise) {
            hare = hare.next;
            lambda++;
        }

        // 使用双指针找入口
        ListNode ptr1 = head;
        ListNode ptr2 = head;

        // ptr2先走lambda步
        for (int i = 0; i < lambda; i++) {
            ptr2 = ptr2.next;
        }

        // 然后同步走，相遇点即为入口
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        return ptr1;
    }

    /**
     * 伪随机数质量检测
     * 线性同余生成器：x = (a * x + c) % m
     */
    public static void randomNumberQualityTest() {
        // 参数设置（使用较短的周期以便演示）
        long a = 25214903917L;
        long c = 11L;
        long m = 1L << 32;  // 2^32
        long seed = 12345L;

        Function<Long, Long> lcg = x -> (a * x + c) % m;

        System.out.println("线性同余生成器参数: a=" + a + ", c=" + c + ", m=" + m);
        System.out.println("种子: " + seed);

        CycleResult result = detectCycle(lcg, seed);
        System.out.println("判圈结果: " + result);
        System.out.println("周期占模数的比例: " + (result.lambda * 100.0 / m) + "%");

        // 生成序列观察
        System.out.println("\n序列前20项:");
        long x = seed;
        for (int i = 0; i < 20; i++) {
            System.out.print(x + " ");
            x = lcg.apply(x);
        }
        System.out.println();
    }

    /**
     * 构建带环链表用于测试
     */
    public static ListNode createCyclicList(int[] values, int cycleStartIndex) {
        if (values == null || values.length == 0) return null;

        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        ListNode cycleNode = null;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
            if (i == cycleStartIndex) {
                cycleNode = current;
            }
        }

        // 连接环
        if (cycleNode != null) {
            current.next = cycleNode;
        }

        return head;
    }

    /**
     * 数学函数判圈示例
     * f(x) = (x^2 + 1) mod n  (常用于Pollard-Rho算法)
     */
    public static void polynomialCycleTest() {
        long n = 10007L;
        Function<Long, Long> f = x -> (x * x + 1) % n;

        System.out.println("\n多项式函数 f(x) = (x^2 + 1) mod " + n);

        for (long seed : new long[]{1, 2, 5, 10}) {
            CycleResult result = detectCycle(f, seed);
            System.out.printf("种子=%d: %s%n", seed, result);
        }
    }

    public static void main(String[] args) {
        System.out.println("========== Brent判圈算法演示 ==========\n");

        // 测试1：伪随机数质量检测
        randomNumberQualityTest();

        // 测试2：多项式函数判圈
        polynomialCycleTest();

        // 测试3：链表环检测
        System.out.println("\n链表环检测测试:");
        int[] listValues = {1, 2, 3, 4, 5, 6, 7, 8};
        ListNode cyclicList = createCyclicList(listValues, 2);  // 3->4->5->6->7->8->3
        ListNode entry = detectLinkedListCycle(cyclicList);
        if (entry != null) {
            System.out.println("发现环！入口节点值: " + entry.val);
            System.out.println("预期入口值: " + listValues[2]);
        } else {
            System.out.println("无环");
        }

        // 测试4：无环链表
        ListNode linearList = new ListNode(1);
        linearList.next = new ListNode(2);
        linearList.next.next = new ListNode(3);
        ListNode noCycle = detectLinkedListCycle(linearList);
        System.out.println("线性链表检测结果: " + (noCycle == null ? "无环（正确）" : "有环（错误）"));
    }
}

算法对比：Floyd vs Brent

在μ（循环前长度）远大于λ（周期）的场景中，Brent算法的优势尤为明显，因为Floyd算法需要兔在循环中绕多圈才能追上龟，而Brent算法通过调整power值减少了不必要的函数求值。

复杂度分析

应用场景

1. Pollard-Rho因数分解：利用序列的循环特性寻找合数的非平凡因子
2. 伪随机数生成器测试：检测PRNG的周期长度，评估其统计质量
3. 链表环检测：经典面试题，判断链表是否存在环并定位入口
4. 函数迭代分析：研究离散动力系统中周期轨道的存在性
5. 密码学分析：评估密钥流生成器的周期特性

Brent判圈算法以其简洁的实现和高效的实际运行性能，成为判圈问题的首选算法。理解其幂次步长策略的巧妙设计，有助于培养对算法常数因子优化的敏感度。