python - 函数递归的时间复杂度

Question

需要帮助证明递归函数的时间复杂度。应该是 2^n。我需要证明是这样的。

def F(n):
    if  n == 0:
        return 0
    else:
        result = 0
        for i in range(n):
            result += F(i)
        return n*result+n`

这是做同样事情的另一个版本。作业说用数组来存储值，试图降低时间复杂度，所以我就是这样做的

def F2(n,array):

    if n < len(array):
        answer = array[n]

    elif  n == 0:
        answer = 0
        array.append(answer)
    else:
        result = 0
        for i in range(n):
              result += F2(i,array)
        answer = n*result+n
        array.append(answer)

    return answer

同样，我正在寻找的是如何找到两个代码片段的复杂性的解释，而不是只对知道答案感兴趣。非常感谢所有帮助。

PS:出于某种原因，我无法让“def F2”留在代码块中...对此感到抱歉

Answer 1

好的，您编写的第一个函数是 Exhaustive Search 的一个示例，您正在探索每个可能的分支，这些分支可以由一组最大 n 的整数组成(您已经在参数中传递了它，并且您正在为此使用 for 循环)。为了向您解释时间复杂度，我将把递归堆栈视为一棵树(要表示递归函数调用堆栈，您可以使用堆栈或使用 n 叉树)

让我们称你为第一个函数F1:

F1(3)，现在集合S中的每一个数都会形成三个分支(集合是到n为止的整数)。我取了 n = 3，因为我很容易为它制作图表。您可以尝试其他更大的数字并观察递归调用堆栈。

    3
   /| \
  0 1  2    ----> the leftmost node is returns 0 coz (n==0) it's the base case 
    |  /\
    0  0 1
         |
         0   ----> returns 0

所以在这里你已经探索了每一个可能的分支。如果您尝试为上述问题编写递归方程，则:

T(n) = 1; n is 0
     = T(n-1) + T(n-2) + T(n-3) + ... + T(1); otherwise

在这里，

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

所以，T(n-1) + T(n-2) + T(n-3) + ... + T(1) = T(n-1) + T(n-1 )

因此，递归方程变为:

T(n) = 1; n is 0
     = 2*T(n-1); otherwise

现在你可以很容易地解决这个递归关系(或者使用马斯特定理来快速解决)。您将获得 O(2^n) 的时间复杂度。

求解递推关系:

T(n) = 2T(n-1)
     = 2(2T(n-1-1) = 4T(n-2)
     = 4(2T(n-3)
     = 8T(n-3)
     = 2^k T(n-k), for some integer `k` ----> equation 1

现在我们给出了 n 为 0 的基本情况，所以让，

n-k = 0 , i.e. k = n;

将k = n放入等式1，

T(n) = 2^n * T(n-n)
     = 2^n * T(0)
     = 2^n * 1; // as T(0) is 1
     = 2^n

所以，T.C = O(2^n)

这就是您如何获得第一个函数的时间复杂度的方法。接下来，如果你观察上面形成的递归树(树中的每个节点都是主问题的子问题)，你会看到节点在重复(即子问题在重复)。因此，您在第二个函数 F2 中使用了内存来存储已计算的值，并且每当子问题再次出现(即重复子问题)时，您都在使用预先计算的值(这样可以节省时间用于一次又一次地计算子问题)。该方法也称为动态规划。

现在让我们看看第二个函数，在这里你返回answer。但是，如果您看到您的函数，那么您正在您的程序中构建一个名为 array 的数组。主要的时间复杂度在那里。计算它的时间复杂度很简单，因为总是只涉及一级递归(或者随便你可以说不涉及递归)，因为每个数字 i 在数字 n 的范围内> 总是小于数字 n，因此第一个 if 条件被执行，控制从那里返回 F2。所以每个调用在调用堆栈中不能超过 2 级。

所以，

Time complexity of second function = time taken to build the array;
                                   = 1 comparisions + 1 comparisions + 2 comparisions + ... + (n-1) comparisions
                                   = 1 + 2 + 3 + ... + n-1
                                   = O(n^2).

让我给你一个简单的方法来更深入地观察这种递归。您可以在控制台上打印递归堆栈并观察函数调用是如何进行的。下面我在打印函数调用的地方编写了您的代码。

代码:

def indent(n):
    for i in xrange(n):
        print '    '*i,

# second argument rec_cnt is just taken to print the indented function properly
def F(n, rec_cnt):
    indent(rec_cnt)
    print 'F(' + str(n) + ')'
    if n == 0:
        return 0
    else:
        result = 0
        for i in range(n):
            result += F(i, rec_cnt+1)
        return n*result+n

# third argument is just taken to print the indented function properly
def F2(n, array, rec_cnt):
    indent(rec_cnt)
    print 'F2(' + str(n) + ')'

    if n < len(array):
        answer = array[n]

    elif n == 0:
        answer = 0
        array.append(answer)
    else:
        result = 0
        for i in range(n):
                result += F2(i, array, rec_cnt+1)
        answer = n*result+n
        array.append(answer)

    return answer


print F(4, 1)
lis = []
print F2(4, lis, 1)

现在观察输出:

 F(4)
      F(0)
      F(1)
               F(0)
      F(2)
               F(0)
               F(1)
                            F(0)
      F(3)
               F(0)
               F(1)
                            F(0)
               F(2)
                            F(0)
                            F(1)
                                             F(0)
96
 F2(4)
      F2(0)
      F2(1)
               F2(0)
      F2(2)
               F2(0)
               F2(1)
      F2(3)
               F2(0)
               F2(1)
               F2(2)
96

在第一个函数调用堆栈中，即 F1，您会看到每个调用都被探索到 0，即我们正在探索每个可能的分支，直到 0 (基本情况)，因此，我们称之为穷举搜索。

在第二个函数调用堆栈中，您可以看到函数调用只有两层深，即它们使用预先计算的值来解决重复的子问题。因此，它的时间复杂度小于F1。