使用递归和循环打印斐波那契级数的时间和空间复杂性

Question

使用递归和循环打印斐波那契级数的时间和空间复杂度（大O表示法）是多少？有一个用于打印斐波那契数的循环，在计算时间和空间复杂度时是否也包括该循环？

我下面的分析正确吗？

public int printFibonacciSeries(int n) {
    if (n <= 1) {
        return n;
    }
    return printFibonacciSeries(n - 1) + printFibonacciSeries(n - 2);
}

public static void main(String[] args) {
    ...
    FibonacciSeries fibonacciSeries = new FibonacciSeries();

    for (int i = 0; i < n; i++) {
        System.out.println("i=" + i + " and "  + fibonacciSeries.printFibonacciSeries(i));
    }
}

我的分析：

• 时间复杂度：O（n 2ⁿ）-因为对于所有n个值，计算斐波那契（计算第n个斐波那契为2ⁿ）
• 空间复杂度：O（1）-递归调用被添加到堆栈中，但一旦执行完成，值就会从堆栈中删除

public void printFibonacciSeriesWithLoop(int n) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        if (i <= 1) {
            arr[i] = i;
        } else {
            arr[i] = arr[i-1] + arr[i-2];
        }
    }
    Arrays.stream(arr).forEach(System.out::println);
}

public static void main(String[] args) {
    ...
    FibonacciSeries fibonacciSeries = new FibonacciSeries();
    fibonacciSeries.printFibonacciSeriesWithLoop(i);
}

我的分析：

• 时间复杂度：O（n n）或O（2n）⟹ O（n）-第一个O（n）用于计算，另一个O（n）用于打印，so 2n，但去掉常数

Answer 1

这可能是一个更好的评论，但因为我没有足够的代表，这里去-

https://youtu.be/_JtPhF8MshA?t=219您可以在这里看到递归实现是如何占用空间O（n）而不是O（1），因为递归树是在它们全部添加和关闭之前构建的！

（注意-链接视频中的时间戳显示了Fac（n）功能的图，但随后在视频Fib功能中也进行了解释，但由于那里没有图，因此附上了此图）