所有斐波那契数从0到n的时间复杂度 [英] Time complexity for all Fibonacci numbers from 0 to n

问题描述

我正在计算此代码的时间复杂度，该代码打印从0到n的所有斐波那契数.根据我的计算， fib()方法采用的是 O(2 ^ n)，由于它被多次称为 i ，所以结果是 O(n * 2 ^ n).但是，这本书说它是 O(2 ^ n).谁能解释为什么这里的时间复杂度是 O(2 ^ n)?

I was calculating the time complexity of this code that prints all Fibonacci numbers from 0 to n. According to what I calculated, the fib() method takes O(2^n) and since it is being called i number of times, so it came out to be O(n*2^n). However, the book says it is O(2^n). Can anyone explain why the time complexity here will be O(2^n)?

这是代码:

void allFib(int n){
    for(int i = 0 ; i < n ; i++){
        System.out.println(i + ": " + fib(i));
    }
}

int fib(int n ){
    if(n <= 0) return 0;
    else if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

推荐答案

我已经弄清楚了我自己理解本书解决方案的方式，希望它能对仍然在挣扎中的人们有所帮助.

I've figured it out my own way to understand the book's solution, hope it helps those who are still struggling.

想象一下，我们现在将其称为allFib(n).

Imagine we now call allFib(n).

由于我们有一个从0到n的for循环，因此将调用以下函数:

Since we have a for loop from 0 to n, the following function will be called:

• i = 0，调用fib(0)
• i = 1，调用fib(1)
• i = 2，调用fib(2)
• ...
• i = n-1，调用fib(n-1)

如前所述，fib(n)将采取O(2 ^ n)= 2 ^ n步因此，

As discussed before fib(n) will take O(2^n) = 2^n steps Therefore,

• i = 0，调用fib(0)需要2 ^ 0步
• i = 1，调用fib(1)进行2 ^ 1步
• i = 2，调用fib(2)进行2 ^ 2步
• ...
• i = n-1，调用fib(n-1)需要2 ^(n-1)个步骤

因此，allFib(n)的运行时间将为

Thus, the runtime of allFib(n) will be

2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^(n-1). *

2^0 + 2^1 + 2^2 + ... + 2^(n-1). *

按照 2个公式的幂之和我们有:

* = 2 ^(n-1 + 1)-1 = 2 ^ n-1.

* = 2^(n-1+1) - 1 = 2^n - 1.

因此它是O(2 ^ n)

Thus it is O(2^n)

这篇关于所有斐波那契数从0到n的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！