提高 Brocard 问题的复杂性？

Question

Brocard 的问题是n! + 1 = m^2。这个问题的解决方案是称为布朗数 (4,5) 等的整数对，其中只有三个是已知的。

Brocard 问题的非常直接的实现：

import math 

def brocard(n,m):
    if math.factorial(n)+1 == m**2:
        return (n,m)
    else:
        return

a=10000

for n in range(a):
    for m in range(a):
        b=brocard(n,m)
        if b is not None:
            print(b)

这个的时间复杂度应该是 O(n^2) 因为嵌套的 for 循环具有不同的变量和任何 math.factorial 算法的复杂性（显然 divide-and-conquer）。有什么方法可以改进 O(n^2)?

还有其他关于 SO 的解释，例如。与我的实现相比，这个的时间复杂度如何？

Answer 1

你的算法是O(n^3)。

您有两个嵌套循环，并且在内部使用 factorial()，本身具有 O(n) 复杂性。

您的算法测试了所有 (n,m) 组合，即使是 factorial(n) 和 m^2 相距很远的组合，例如n=1 和 m=10000.

您总是在循环内部重新计算 factorial(n)，尽管它独立于内部循环变量 m。因此，它可以移到内部循环之外。

而且，您可以逐步进行计算，而不是总是从头开始计算 factorial(n)。每当您将 n 递增 1 时，您可以将前一个阶乘乘以 n。

另一种更好的方法是不使用嵌套循环，而是始终将 n 和 m 保持在一个数字范围内，以便 factorial(n) 接近 m^2，以避免检查相差很大的数字对。我们可以通过决定接下来要递增哪个变量来做到这一点。如果阶乘较小，则下一个 brocard 对需要更大的 n。如果正方形较小，我们需要更大的 m.

在伪代码中，那将是

n = 1; m = 1; factorial = 1;
while n < 10000 and m < 10000
    if factorial + 1 == m^2
        found a brocard pair
        // the next brocard pair will have different n and m,
        // so we can increment both
        n = n + 1
        factorial = factorial * n
        m = m + 1
    else if factorial + 1 < m^2
        // n is too small for the current m
        n = n + 1
        factorial = factorial * n
    else
        // m is too small for the given n
        m = m + 1

在每次循环迭代中，我们要么递增n，要么递增m，因此我们最多可以进行 20000 次迭代。算法中没有内循环。我们有 O(n)。因此，这对于 n 和 m 到数百万范围应该足够快。

P.S。还有一些可能的优化。

阶乘（在 n=1 之后，已知没有 brocard 对）总是偶数，所以 m^2 必须是奇数才能满足 brocard 条件，这意味着我们总是可以将 m 递增 2，跳过偶数中间的数字。

对于较大的 n 值，阶乘比平方增加得快得多。因此，不是递增 m 直到其平方达到 factorial+1 值，我们可以重新计算下一个合理的 m 作为 factorial+1.

的整数平方根

或者，使用平方根方法，只计算 factorial(n) 的整数平方根，并检查它是否匹配，而不对 m 进行任何增量步骤。

提高 Brocard 问题的复杂性？

Improving the complexity of Brocard's problem?

performance

time-complexity

python-3.x