计算算法的时间复杂度

Question

所以这是一个算法，它应该 return 给定多项式的 P(x) 的多项式值与任何给定的 x。

A[]是系数数组，P[]是x数组的幂

（例如 x^2 +2*x + 1 将有：A[] = {1,2,1} , P[]= {2,1,0}）

此外，recPower() = O(logn)

int polynomial(int x, int A[], int P[], int l, int r)
{
    if (r - l == 1)
        return ( A[l] * recPower(x, P[l]) ) + ( A[r] * recPower (x, P[r]) );
    int m = (l + r) / 2;
    return polynomial(x, A, P, l, m) + polynomial(x, A, P, m, r);
}

我该如何计算这个时间复杂度？由于 if 语句，我感到困惑。我不知道递归关系是什么。

Answer 1

这可能有帮助：

T(#terms) = 2T(#terms/2) + a
T(2) = 2logn + b

其中a和b是常数，#terms是指多项式的项数。这个递归关系可以用马斯特定理或递归树法求解。

Answer 2

以下观察可能会有所帮助：一旦我们有 r = l + 1，我们就会花费 O(logn) 时间，然后我们就完成了。

我的回答需要很好地理解 Recursion Tree。所以明智地进行。

所以我们的目标是找到：在多少次迭代之后我们能够知道我们有 r = l + 1？

让我们找出答案：

关注return polynomial(x, A, P, l, m) + polynomial(x, A, P, m, r);

让我们先考虑左函数polynomial(x, A, P, l, m)。需要注意的关键是 l 在递归调用的所有后续左函数中保持不变。

左函数是指polynomial(x, A, P, l, m)，右函数是指

polynomial(x, A, P, m, r).

对于左函数 polynomial(x, A, P, l, m)，我们有：

第一次迭代

l = l and r = (l + r)/2

第二次迭代

l = l and r = (l + (l + r)/2)/2

这意味着

r = (2l + l + r)/2

第三次迭代

l = l and r = (l + (l + (l + r)/2)/2)/2

这意味着

r = (4l + 2l + l + r)/4

第四次迭代

l = l and r = (l + (l + (l + (l + r)/2)/2)/2)/2

这意味着

r = (8l + 4l + 2l + l + r)/8

这意味着在第n次迭代中我们有：

r = (l(1 + 2 + 4 + 8 +......2^n-1) + r)/2^n

和终止条件是r = l + 1

求解(l(1 + 2 + 4 + 8 +......2^n-1) + r)/2^n = l + 1，我们得到

2^n = r - l

这意味着n = log(r - l)。有人可能会说，在所有后续的左函数调用中，我们忽略了另一个调用，即右函数调用。原因是这样的：

因为在正确的函数调用中我们 l = m，其中 m 已经是一个减少的，因为我们取均值，而 r = r 甚至更平均，这渐近地不会对时间复杂度。

因此我们的 递归树将具有最大深度 = log(r - l)。确实并非所有级别都将完全填充，但为了简单起见，我们在 渐近分析 中假设这一点。所以在达到 log(r - l) 的深度后，我们调用函数 recPower，这需要 O(logn) 时间。深度 log(r - l) 处的节点总数（假设上面的所有级别都已满）为 2^(log(r - l) - 1)。对于单个节点，我们需要 O(logn) 时间。

因此我们有总时间 = O( logn*(2^(log(r - l) - 1)) ).

计算算法的时间复杂度

Calculate time complexity of algorithm

algorithm

time-complexity

polynomials