java - BigInteger 的 nextProbablePrime() 的时间复杂度

Question

nextProbablePrime()方法的时间复杂度是BigInteger多少？

Answer 1

如果您查看源代码，您会看到有 2 个不同的分支：

• 如果起点很小，则使用Miller-Rabin + Lucas Lehmer，误报的概率（对于 MillerRabin）低于 2^-100。候选者在每个循环中增加 2，直到找到匹配项。
• 如果它很大，则使用位筛代替。与上述相同的素数测试用于测试素数候选者。

对于大 O 复杂性，只有大的情况很重要。Miller-Rabin 需要对 n 位数字进行 k 次迭代（在本例中，k=100）的 O(kn^2 log n log log n) 操作，而 Lucas 则需要 O(n^2 log n log log n) - Lehmer（根据维基百科）。因此，在忽略常数因子 (k) 后，对每个候选者运行的素性测试的大 O 复杂度为O(n^2 log n log log n)

真正的时间复杂度必须考虑素数之间的差距- 如果您必须对大量素数进行素性测试（并且差距随着起点的增加而增加），那么您的复杂性肯定会受到影响。如果测试候选人的复杂度为 C(n)，而您必须测试 G(n) 候选人，那么您的复杂度将为G(n) * C(n)。在这一点上，我可以研究 Java 中使用的筛子的实现。

但是对于 Big-Oh 复杂性的原始问题，有一个更简单、正确的答案：Java 将查看的素数大小有一个硬性上限。因此，由于存在一个最大值 n ，超过该最大值的所有调用都会n.nextProbablePrime()引发异常，因此此方法为 O(1)。