改善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)吗？

在像this这样的网站上还有其他解释。与我的实现相比，它的时间复杂度如何？

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来说，这应该足够快到百万级了。

附注:仍然有一些优化的可能性。

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

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

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