递归函数的时间复杂度

Question

递归函数的时间复杂度

pythonalgorithmrecursiontime-complexitydynamic-programming

3

需要帮助证明递归函数的时间复杂度。据说是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

我需要解释如何找到这两段代码的复杂度，而不只是知道答案。非常感谢任何帮助。

注：由于某些原因，我无法让“def F2”保留在代码块中......对此很抱歉。

- Karim Kamel

1

如果您能简要解释一下您的函数应该做什么，那将会很有帮助。特别是当它们的名称像 F 和 F2 一样时... - juanpa.arrivillaga

1

你可以通过数学归纳法证明2^n的事情。 - Paul Panzer

这实际上是一个相对复杂的数学问题，如果您没有得到答案，可能是因为它超出了本网站更技术范围之外（例如如何实现算法，为什么实现不起作用，如何在语言y中执行x等）。如果您没有得到答案，那就是原因。我建议查看课程提供的确定递归方法的大O的方法。例如，您知道 T(n)=T(n-1)+T(n-2)+...+T(1)+T(0)+O(1) 从那里开始。 - Garrett Gutierrez

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Amit Upadhyay · Accepted Answer

好的，你写的第一个函数是“穷举搜索”（Exhaustive Search）的一个例子，您正在探索从一组整数（这些整数可以是从 1 到 n 的所有整数）中可以形成的每个可能的分支（您正在使用 for 循环进行此操作）。为了向您解释时间复杂度，我将把递归栈表示为树形结构（要表示递归函数调用堆栈，您可以使用堆栈或使用 n 叉树）。

让我们称您的第一个函数为 F1：

F1(3)，现在对于集合 S（即从 1 到 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

现在你可以轻松解决这个递归关系（或者使用Masters定理进行快速求解）。你将得到时间复杂度为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的数组。主要的时间复杂度就在那里。计算它的时间复杂度很简单，因为始终只涉及一级递归（或者你可以随意地说没有递归涉及），因为在n数范围内的每个数字i总是小于数字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)

现在观察输出结果：

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

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