java - 如何提高大数 java 递归实现的时间复杂度？

Question

我有递归

T(1) = 2 ^ k
T(2) = 2 * T(1) - 1
T(3) = 2 * T(2) - 1
T(4) = 2 * T(3) - 2
T(5) = 2 * T(4) - 4
T(6) = 2 * T(5) - 8

..

T(10) = 2 * T(9) - 128 

..

对于 n >= 3 我们可以看到:

T(n) = 2 * T(n-1) - (2 ^ (n-3))

条件:

1 <= n <= 2.000.000.000
0 <= K <= 40
k < n

因为 n 可能非常大，所以我通过使用 BigInteger 迭代实现了这个递归(递归函数返回 StackOverflow 错误)，但是对于 n = 200.000 和 k = 39 程序需要 15 秒来计算 T(n) 并且它必须花费更少max(n) 和 max(k) 为 5 秒。我需要的不是 T(n)，而是 T(n) % 40009 那么我怎样才能减少这个递归呢？

Answer 1

让我们尝试转换术语:

T(1) = 2 ^ k
T(2) = 2 * 2 ^ k - 1
T(3) = 2 * 2 * 2 ^ k - 2 * 1 - 1 = 2 ^ 2 * 2 ^ k - 2 ^ 1 - 1
T(4) = 2 * 2 * 2 * 2 ^ k - 2 * 2 * 1 - 2 = 2 ^ 3 * 2 ^ k - 2 ^ 2 - 2 ^ 1
T(5) = 2 * 2 * 2 * 2 * 2 ^ k - 2 * 2 * 2 * 1 - 2 * 2 - 4 = 2 ^ 4 * 2 ^ k - 2 ^ 3 - 2 ^ 2 - 2 ^ 2
T(6) = 2 * 2 * 2 * 2 * 2 * 2 ^ k - 2 * 2 * 2 * 2 * 1 - 2 * 2 * 2 - 2 * 4 - 8 = 2 ^ 5 * 2 ^ k - 2 ^ 4 - 2 ^ 3 - 2 ^ 3 - 2 ^ 3

如您所见，我们可以将其分为 2 个术语:第一:

T(n) = 2 ^ (n-1) * 2 ^ k + ... = 2 ^ (k + n - 1) + ...

第二个:

T(n) = ... + -2^(n-2) - (n - 2) * 2^(n-3)

因此您可以通过以下方式计算无递归项:

T(n) = 2^(k + n - 1) - 2^(n-2) - (n - 2) * 2^(n-3)

然后您可以对项进行因式分解并应用模数来减少数字:

T(n) = 2^(n - 3) * (2^(k + 2) - 2^(1) - (n - 2)) = 2^(n - 3) * (2^(k + 2) - n)

现在您可以应用模数:

T(n) modulo 40009 = ((2^(n - 3) modulo 40009) * (2^(k + 2) - n) modulo 40009) modulo 40009

这里是 BigInteger 的实现:

static long calc(int n, int k, int m) {
    BigInteger left = new BigInteger("2");
    BigInteger nBig = new BigInteger(String.valueOf(n - 3));
    BigInteger mod = new BigInteger(String.valueOf(m));
    left = left.modPow(nBig, mod);

    BigInteger right = new BigInteger("2");
    right = right.pow(k + 2);
    right = right.subtract(new BigInteger(String.valueOf(n)));
    right = right.mod(mod);

    left = left.multiply(right);
    left = left.mod(mod);

    return left.longValue();
}

编辑:添加初始转换