算法的设计与分析：递归关系

Question

我对解决这种递归关系非常怀疑。谁能为我提供解决方案？

关系：

T（n）=求和i = 1到I N T（i）+1 ......，

什么是bigOh订单？

Answer 1

取一阶差异可以让你摆脱总和。

T(n) - T(n-1) = (Sum(1<=i<n: T(i)) + 1) - (Sum(1<=i<n-1: T(i)) + 1) = T(n-1)

于是

T(n) = 2.T(n-1)

Answer 2

递归关系描述了一系列数字。早期术语是明确指定的，后面的术语表示为其前辈的函数。作为一个简单的例子，这个重复描述了序列1,2,3等：

    void Sample(int n)
    {
        if (n > 0) {
            Sample(n-1);
            System.out.println('here');
        } else {
            return 1;
        }
    }

    Sample(3);

这里，第一项定义为1，每个后续项比其前一项多一个。为了分析递归关系，我们需要知道每行代码的执行时间，在上面的例子中：

    void Sample(int n)
    {
               if (n > 0) {
     // T(n-1)      Sample(n-1);
     // 1           System.out.println('here');
               } else {
                   return 1;
               }
    } 

我们将T（n）定义为：

为了解决T(n)= T(n-1)+1，如果我们知道什么是T(n-1)，那么我们可以替换它并得到答案，让我们用n代替它，我们将：

T(n-1)= T(n-1-1)+1 => T(n-2)+1
//in continue
T(n)=[T(n-2)+1]+1 => T(n-2)+2
//and again
T(n)=[T(n-3)+2]+1 => T(n-3)+3
.
.
.
// if repeat it k times, while it ends
T(n)= T(n-k)+k

如你所见，每步增加1，如果我们去k次，那么T(n)= T(n-k)+k。现在，我们需要知道最小的值（当函数停止时，总是必须停止一个点）。在这个问题中，零是递归堆栈的结束。我们假设我们去k时间达到零，解决方案将是：

// if n-k is final step
n-k = 0 => n = k
// replace k with n
T(n)= T(n-n)+n => T(n)= T(0)+n;
// we know
T(0) = 1;
T(n) = 1+n => O(n)

大O是n，这意味着这种递归算法在最坏的情况下是n次。