recursion - 递归方法的大O

Question

我很难确定简单的递归方法的大O。我无法确定多次调用一个方法时会发生什么。我会更具体地说明我的困惑 Realm ，但此刻我正试图回答一些硬件问题，而不是不想作弊，我要求对此帖子做出回应的所有人提出一种简单的递归方法，提供上述方法的大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)

诚然，这不是很正式，但是希望通过这种方式您可以有所体会。