在 O(logn) 时间内求出从 k= 0 到 n 的 x^k 的总和

Question

所以我的问题是如何更具体地在 C 中执行此操作。我知道 O(logn) 通常意味着我们将通过以某种方式拆分参数之一来使用递归。

我要实现的是xⁿ的k = 0到n的总和。例如 exponent_sum(x, n) 将是这种情况下的参数。

然后，

exponent_sum(4, 4) 将是 4⁰ + 4¹ + 4² + 4³ + 4⁴ = 341.

我不知道从哪里开始。一些提示将不胜感激。

Answer 1

查看总和的一种方法是将数字视为以 x 为底且全为 1 的数字。

例如，4⁴ + 4³ + 4² + 4¹ + 4⁰ 是以 4 为基数的 11111.

在任何基数中，一串 1 将等于 1，后跟一串相同数量的 0 减 1，除以基数减 1。

例如：

以 10 为基数：(1000 - 1) / 9 = 999 / 9 = 111
以 16 为基数：(0x10000 - 1) / 0xF = 0xFFFF / 0xF = 0x1111
以 8 为基数：(0100 - 1) / 7 = 077 / 7 = 011

等等

所以把这些放在一起，我们可以概括一下

exponent_sum(x, n) = (x ^{(n + 1)} - 1) / (x - 1)

例如，exponent_sum(4, 4) = (4⁵ - 1) / 3 = 1023 / 3 = 341

所以它的大 O 复杂度将与计算 xⁿ

相同

Answer 2

为了完整起见，让我再补充一个证明：

s = 1 + x¹ + x² + ... + xⁿ

然后

xs = x(1 + x¹ + x² + ... + xⁿ) = x¹ + x² + ... + xⁿ + xⁿ⁺¹ = s - 1 + xⁿ⁺¹

求解 s

(x - 1)s = xⁿ⁺¹ - 1,

s = (xⁿ⁺¹ - 1)/(x - 1)

Answer 3

另一种解法是这样的：假设和S写成

S = 1 + x + x^2 + ... + x^k

然后，如果我们将它的两边都乘以 x，我们得到

S*x = x * (1 + x + x^2 + ... + x^k)
    = x + x^2 + ... + x^k + x^(k+1)

然后两边加1

S*x + 1 = 1 + x + x^2 + ... + x^k + x^(k+1)
        = (1 + x + x^2 + ... + x^k) + x^(k+1)
        = S + x^(k+1)

这意味着

S*x - S = x^(k+1) - 1
S*(x - 1) = x^(k+1) - 1

所以

S = (x^(k+1) - 1) / (x - 1)

Answer 4

运用几何级数理论。其中

sum = (first-term(pow(common-ratio,number-of-terms)-1))/(common-ratio-1);
here first-term is obviously 1;
Common-ratio= number itself;
number-of-terms=number+1;

但是共同比率应该大于1；对于

Common-ratio=1;
Sum=number*number-of-terms.

Answer 5

您可以直接计算总和，而无需使用等比级数公式。这样做的优点是不需要除法（例如，如果您想使代码适应 return 结果对某个大数取模，则这是必需的）。

设S(k)为x^0 + ... + x^{k-1}之和，满足递归关系：

S(1)    = 1
S(2n)   = S(n) * (1 + x^n)
S(2n+1) = S(n) * (1 + x^n) + x^{2n}

使用这些，唯一的困难是安排保持 xp 的运行值用作 x^n。否则该算法非常类似于通过平方求幂的自下而上实现。

#include <inttypes.h>
#include <stdio.h>
#include <stdint.h>

int64_t exponent_sum(int64_t x, int64_t k) {
    int64_t r = 0, xp = 1;
    for (int i = 63; i >= 0; i--) {
        r *= 1 + xp;
        xp *= xp;
        if (((k + 1) >> i) & 1) {
            r += xp;
            xp *= x;
        }
    }
    return r;
}

int main(int argc, char *argv[]) {
    for (int k = 0; k < 10; k++) {
        printf("4^0 + 4^1 + ... + 4^%d = %" PRId64 "\n", k, exponent_sum(4, k));
    }
    return 0;
}

在 O(logn) 时间内求出从 k= 0 到 n 的 x^k 的总和

Finding sum of x^k from k= 0 to n in O(logn) time

c

algorithm

big-o