c - 在 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< sup>3 + 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ⁿ

相同