递归方法的大O [英] Big O of Recursive Methods

问题描述

我很难确定简单的递归方法的大O.我无法确定多次调用一个方法时会发生什么.我会更具体地说明我的困惑领域，但此刻我正试图回答一些硬件问题，而不是不想作弊，我要求对此帖子做出回应的所有人都想出一种简单的递归方法，提供上述方法的大O值的简单说明. (最好使用Java ...一种我正在学习的语言.)

I'm having difficulty determining the big O of simple recursive methods. I can't wrap my head around what happens when a method is called multiple times. I would be more specific about my areas of confusion, but at the moment I'm trying to answer some hw questions, and in lieu of not wanting to cheat, I ask that anyone responding to this post come up with a simple recursive method and provide a simple explanation of the big O of said method. (Preferably in Java... a language I'm learning.)

谢谢.

推荐答案

您也可以递归定义顺序.例如，假设您有一个函数f.要计算f(n)需要k步.现在您要计算f(n + 1).假设f(n + 1)调用一次f(n)，则f(n + 1)采取k +一些恒定的步长.每次调用将额外花费一些恒定的步骤，因此此方法为O(n).

You can define the order recursively as well. For instance, let's say you have a function f. To calculate f(n) takes k steps. Now you want to calculate f(n+1). Lets say f(n+1) calls f(n) once, then f(n+1) takes k + some constant steps. Each invocation will take some constant steps extra, so this method is O(n).

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

Now look at another example. Lets say you implement fibonacci naively by adding the two previous results:

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)

Now lets say you can calculate fib(n-2) and fib(n-1) both in about k steps. To calculate fib(n) you need k+k = 2*k steps. Now lets say you want to calculate fib(n+1). So you need twice as much steps as for fib(n-1). So this seems to be O(2^N)

诚然，这不是很正式，但希望以此方式您可以有所体会.

Admittedly, this is not very formal, but hopefully this way you can get a bit of a feel.

这篇关于递归方法的大O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！