大O的递归方法

我很难确定简单递归方法的大O.当我多次调用某个方法时，我无法将自己的头围绕在发生什么情况。我会更加具体地讨论我的混乱领域，但是现在我试着回答一些问题，并且不想欺骗，我要求任何回复此帖的人都会提出一个简单的递归方法，并且提供所述方法的大O的简单解释。（最好在Java中......我正在学习的语言。）大O的递归方法

谢谢。

来源

2012-07-31 user1333461

这实际上与递归没有多大关系，以及与大O表示法有关的所有事情。如果你可以递归地写它，你可以迭代地写它 – MStodd 2012-07-31 23:00:47

@ MStodd不一定。尝试迭代遍历二叉树。 – Drise 2012-07-31 23:01:41

@Drise你需要一个堆栈，但它是可能的。递归只是将堆栈隐藏在调用堆栈中。 – 2012-07-31 23:04:39

您也可以递归地定义顺序。例如，假设你有一个函数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) }

现在让我们说你可以计算FIB（N-2）和FIB（N-1）无论是在约k步。要计算fib（n），您需要k + k = 2 * k个步骤。现在让我们说你想计算fib（n + 1）。所以你需要两倍于fib（n-1）的步数。所以这似乎是O（2^N）

不可否认，这不是很正式，但希望这样你可以有一点感觉。

来源

2012-07-31 23:10:10 markijbema

一个概念化的好方法。再次投票你 - 但我还没有达到15分。 – user1333461 2012-07-31 23:49:06

@ user1333461现在你可以:) – oleksii 2012-08-06 13:47:44

太棒了 - 谢谢！ – user1333461 2012-08-09 19:25:51

你可能想引用主定理来找到递归方法的大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))

你可以看到，依次归并的每一个呼叫电话2个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））。

来源

2012-07-31 23:15:08

我会为你投票，但是我的名声不够高。这确实有帮助。我将着重于主定理。谢谢。 – user1333461 2012-07-31 23:50:15

@ user1333461如果这有帮助，请给他答案。 – Drise 2012-08-01 21:01:32

我如何接受他的回答？ – user1333461 2012-08-09 19:06:21

大O的递归方法

回答

相关问题