递归方法的大O

Question

我很难确定简单递归方法的大O。我不知道当一个方法被多次调用时会发生什么。我想更具体地谈谈我的困惑领域，但目前我正试图回答一些硬件问题，为了不想作弊，我要求任何回复本文的人提出一个简单的递归方法，并对所述方法的大O进行简单解释。（最好是Java语言……我正在学习的一种语言。）

谢谢你。

Answer 1

你可能想参考寻找递归方法的大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调用依次调用两个以上的mergeSorts，其长度为原始长度的1/2。我们知道合并过程所需的时间与被合并的值的数量成比例。

递归关系为T（n）=2*T（n/2）O（n）。这两个来自2个调用，n/2来自每个调用，每个调用的元素数只有一半。然而，在每个级别上都有相同数量的元素n需要合并，因此每个级别上的恒定功为O（n）。

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

Answer 2

您也可以递归地定义顺序。例如，假设你有一个函数f。计算f（n）需要k步。现在要计算f（n 1）。假设f（n1）调用f（n）一次，那么f（n1）需要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）

诚然，这不是很正式，但希望通过这种方式你能有点感觉。