相关疑难解决方法(0)

这是我作业的一个问题.我不太清楚如何解决这样的问题.

If T(n) = nT(n - 1) and T(1) = 3, then
a) T(n) = O(n^n)
b) T(n) = ?(n!)
c) T(n) = O(2^(nlogn))
d) none of the above

我不需要这个问题的确切答案(因为它的功课),但我想知道告诉递归函数的界限的方法.

因此,我在Java中有一个递归方法来获取'n'的斐波纳契数 - 我唯一的问题是:时间复杂度是多少？我认为这是O(2 ^ n),但我可能会弄错？(我知道迭代更好,但这是一个练习)

public int fibonacciRecursive(int n)
{
    if(n == 1 || n == 2) return 1;
    else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}

编写下面的代码来计算前70个斐波纳契数.我有两个问题:

1)为什么程序对于每个连续的值变得越来越慢i？是因为调用具有高数字的函数会导致大量内存占用.

2)我可以使用什么技术或编码方案来加速运行时的程序计算？

#include <iostream>

int fib(int n) {
  if (n == 1 || n == 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

void main() {
  for (int i = 1; i<70; i++)
    cout << " fib(" << i << ") = " << fib(i) << endl;
}

这不是家庭作业。在下面的代码中：

(defparameter nums '())

(defun fib (number)
  (if (< number 2)
      number
    (push (+ (fib (- number 1)) (fib (- number 2))) nums))
  return nums)

(format t "~a " (fib 100))

由于我对Common Lisp完全没有经验，所以我对为什么该函数不返回值感到困惑。我正在尝试打印斐波那契数列的第一个“ n”值，例如100。

谢谢。

我用两种不同的方式计算斐波那那排.为什么fib1的执行时间比fib2长得多？

public class RecursionTest {

    @Test
    public void fib1() {
        long t = System.currentTimeMillis();

        long fib = fib1(47);

        System.out.println(fib + "  Completed fib1 in:" + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();

        fib = fib2(47);

        System.out.println(fib + "  Completed fib2 in:" + (System.currentTimeMillis() - t));

    }


    long fib1(int n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            return fib1(n - 1) + fib1(n - 2);
        }
    }


    long fib2(int n) {
        return n == …