给定递归算法解决递归关系并给出最坏情况下的时间复杂度，这是正确的吗？

Question

求时间复杂度，在最坏情况下，在 n = 2N 的函数中， N >=0.

找到递归关系并求解。

 public static void xpto(v, n){
    if (n <= 1) 
        return;
    n=n/2;
    for(i=0;i<n;i=i+1) 
        v[i] = v[2i] + v[2i +1];
    xpto(v, n);
}

T(1) = 1

代入递归方程：

T(n) = 1 + 1 + (n + 1) + n + T(n/2)

T(n) = 3 + 2n + T(n/2)

T(n/2) = 3(2) + 2n(2) + T(n/4)

T(n/4) = 3(3) + 2n(3) + T(n/8)

T(n/8) = 3(4) + 2n(4) + T(n/16)

找到模式

T(n/8) = 3(4) + 2n(4) + T(n/2^4)

一般递归 k:

T(n) = 3(k) + 2n(k) + T(n/2^k)

if T(1) = 1 and T(n/2^k) we need to change 2^k by n, this means:

2^k = n

T(n) = 3(log n) + 2n(log n) + 1

递归关系求解

时间复杂度，最坏情况下为O(log(n))

问题：

我这样做对吗？
n = 2N , N >=0 是什么函数？

Answer 1

我不确定你是怎么得到常量的，但为了简单起见，我们假设操作 v[i] = v[2i] + v[2i +1]; 的成本为 1，其他一切都是免费的。（在不影响后面计算概念的情况下可以很方便的调整）。

基于此，

T(n) = n/2 + T(n/2)

据此，我们可以将master theorem case 1与c=1, a=1,b=2结合使用，得出T(n)在Theta(n^1)=Theta(n)

中

Answer 2

首先，如果您得到：T(n) = 3(log n) + 2n(log n) + 1 作为您的最终解决方案，那么最坏情况下的复杂度不会是 log n，而是 n(log n)，因为术语 2n(log n) .

根据你最初的递归关系：T(n) = 3 + 2n + T(n/2) 我做了以下事情：

Assume n = 2^k and g(k) = T(n) such that:
g(k) = g(k-1) + 2*2^k + 3 (from simply substituting n=2^k and change of function)
g(k) = sum(i=1 to k) of (2*2^i + 3)
g(k) = 2 * (sum(i=1 to k) of (2^i)) + 3k

Using geometric progression, common ratio = 2:
g(k) = 2 * (2(1-2^k) / (1-2)) + 3k
g(k) = -4 + 4*2^k + 3k

Since we initially assumed n = 2^k, this means k = log n:
T(n) = -4 + 4n + 3(log n)
Hence the worst case complexity is O(n)

对于你问题的第二部分：

n = 2N 其中 N >= 0 仅表示 n 是一组偶数因为任何正整数乘以 2 都是偶数。

给定递归算法解决递归关系并给出最坏情况下的时间复杂度，这是正确的吗？

Given a recursive algorithm solve the recurrence relation and give the time complexity in worst case, this is correct?

java

algorithm

recursion

recurrence

time-complexity