递归方法的时间复杂度Big O

Question

我在确定简单递归方法的大O时遇到了困难，我无法理解当一个方法被多次调用时会发生什么。我想更具体地说明我的困惑，但现在我正在尝试回答一些作业问题，为了不想作弊，我要求回复此帖子的任何人都提供一个简单的递归方法并提供该方法的大O的简单解释。(最好用我正在学习的Java语言...)

谢谢。

- user1333461

---

这与递归实际上没有太大关系，而与大O符号有着千丝万缕的联系。如果你可以用递归方式编写它，那么你也可以用迭代方式编写它。 - MStodd

@MStodd 不一定。尝试使用迭代方式遍历二叉树。 - Drise

你需要一个堆栈，但这是可能的。递归只不过是在调用栈内隐藏了堆栈。 - Sam Mussmann

@Drise 或许稍后再回答。重点是帮助原帖作者完善问题。 - MStodd

可能是使用递归方法的大O符号表示法的重复问题。 - user2284570

Answer 1

你也可以递归地定义顺序。例如，假设你有一个函数 f，计算 f(n) 需要 k 步。现在你想计算 f(n+1)。假设 f(n+1) 调用 f(n) 一次，则 f(n+1) 需要 k + 一些常数步骤。每次调用都需要额外的一些常数步骤，因此该方法的时间复杂度为 O(n)。

现在再看另一个例子。假设你通过将前两个结果相加来朴素地实现 fibonacci:

fib(n) = { return fib(n-1) + fib(n-2) }

现在假设你可以在约k个步骤内计算出fib(n-2)和fib(n-1)的值。为了计算fib(n)，你需要2*k个步骤。现在假设你想要计算fib(n+1)，那么你需要的步骤数是fib(n-1)的两倍，因此这似乎是O(2^N)。

诚然，这并不是非常正式，但希望通过这种方式你可以有一些感觉。

- markijbema

---

一个很好的概念化方法。再次感谢你的帮助，但我还没有达到15分，无法点赞。 - user1333461

在此添加一个有用的链接：https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1176/handouts/midterm/5-BigO.pdf - AKV

Answer 2

你可能需要参考主定理来找到递归方法的大O表示法。这里是维基百科文章链接：http://en.wikipedia.org/wiki/Master_theorem。

你可以将递归问题看作一棵树。然后，考虑每个层级的工作量。问题通常可以分为三类，即根重型（第一次迭代>>其余部分），平衡型（每个层级具有相等的工作量）和叶重型（最后一次迭代>>其余部分）。

以归并排序为例：

define mergeSort(list toSort):
    if(length of toSort <= 1):
        return toSort
    list left = toSort from [0, length of toSort/2)
    list right = toSort from [length of toSort/2, length of toSort)
    merge(mergeSort(left), mergeSort(right))

你可以看到，每次调用mergeSort都会再次调用1/2原始长度的2个更多的mergeSort。我们知道合并过程所需的时间与正在合并的值的数量成比例。

递归关系式为T(n) = 2*T(n/2)+O(n)。这个2来自于2个调用，n/2来自于每个调用仅具有一半的元素数量。然而，在每个级别上，需要合并的元素n数量相同，因此每个级别的常量工作是O(n)。

我们知道工作被平均分配（每个深度都是O(n)），树的深度是log_2(n)，因此递归函数的大O是O(n*log(n))。

- Calvin Jia

---

我想给你点赞，但我的声望还不够高。这确实有帮助。我会专注于主定理。谢谢。 - user1333461

@user1333461 如果这篇回答有帮助，请接受他的回答。 - Drise