recursion - 递归方法的大 O

Question

我很难确定简单递归方法的大 O。当一个方法被多次调用时，我无法理解会发生什么。我会更具体地说明我的困惑领域，但目前我正在尝试回答一些硬件问题，而不是不想作弊，我要求任何回复这篇文章的人提出一个简单的递归方法和提供对所述方法的大O的简单解释。（最好用 Java ......我正在学习的一种语言。）

谢谢你。

Answer 1

您也可以递归定义顺序。例如，假设您有一个函数 f。计算 f(n) 需要 k 步。现在您要计算 f(n+1)。假设 f(n+1) 调用 f(n) 一次，然后 f(n+1) 需要 k + 一些恒定步骤。每次调用都会额外采取一些恒定的步骤，所以这个方法是 O(n)。

现在看另一个例子。假设您通过添加前面的两个结果来天真地实现斐波那契：

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

现在假设您可以在大约 k 步中计算 fib(n-2) 和 fib(n-1)。要计算 fib(n)，您需要 k+k = 2*k 步。现在假设您要计算 fib(n+1)。因此，您需要的步数是 fib(n-1) 的两倍。所以这似乎是 O(2^N)

诚然，这不是很正式，但希望通过这种方式你可以得到一点感觉。

Answer 2

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

你想把递归问题想象成一棵树。然后，考虑树的每个级别和所需的工作量。问题通常分为 3 类，根重（第一次迭代 >> 树的其余部分）、平衡（每个级别有相等的工作量）、叶重（最后一次迭代 >> 树的其余部分）。

以归并排序为例：

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 又会再调用 2 个原长度 1/2 的 mergeSort。我们知道合并过程所花费的时间与被合并的值的数量成正比。

则递归关系为 T(n) = 2*T(n/2)+O(n)。这两个来自 2 个调用，而 n/2 来自每个调用，只有一半的元素。然而，在每一层都有相同数量的元素 n 需要合并，所以每一层的常数工作是 O(n)。

我们知道工作是均匀分布的（每个深度 O(n)），树的深度是 log_2(n)，所以递归函数的大 O 是 O(n*log(n))。