试图显示斐波那契的递归调用次数等于 Big O

Question

我有这个代码来计算递归调用的次数，并显示它大约等于 O(2^n)，正如众所周知的斐波那契数；

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int c=0;

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

int main(int argc, char * argv[]) {

    int i;
    for(i = 1 ; i < 10 ; i++) {
        c=0;
        int f=fib(i);
        printf("fib(%d) = %d,\tc = %d,\t2^%d = %f\n", i, f, c, i, pow(2,i));
    }

    return 0;
}

这是输出；

fib(1) = 1,     c = 1,  2^1 = 2.000000
fib(2) = 1,     c = 1,  2^2 = 4.000000
fib(3) = 2,     c = 3,  2^3 = 8.000000
fib(4) = 3,     c = 5,  2^4 = 16.000000
fib(5) = 5,     c = 9,  2^5 = 32.000000
fib(6) = 8,     c = 15, 2^6 = 64.000000
fib(7) = 13,    c = 25, 2^7 = 128.000000
fib(8) = 21,    c = 41, 2^8 = 256.000000
fib(9) = 34,    c = 67, 2^9 = 512.000000

这是怎么回事？

Answer 1

如果我没理解错的话，您想知道为什么 c 的值和相应的值 2ⁿ 没有您预期的那么接近。

原因是调用树不平衡，所以 O(2ⁿ) 只是一个松散的上限。调用次数的下限为 Ω(2<sup>n/2</sup>).

如图所示：您为 n=6 计算的数字是正确的。也可以看到调用树不平衡

试图显示斐波那契的递归调用次数等于 Big O

Trying to show number of recursive calls for fibonacci is equal to Big O

big-o

fibonacci