相关疑难解决方法(0)

我理解Big-O表示法,但我不知道如何为许多函数计算它.特别是,我一直试图弄清楚Fibonacci序列的幼稚版本的计算复杂性:

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

Fibonacci序列的计算复杂度是多少以及如何计算？

我似乎不理解这段代码的输出:

function fib(x) {
  return (x === 0 || x === 1) ? x : fib(x - 1) + fib(x - 2);
}

fib(7);
// output is 13

这是我的思考过程:

• 将int传递给函数并检查它是0还是1
• 如果它为0或1,则继续返回传递的值
• 如果它不是0或1,则从7减去1,然后从7减去2
• 返回输出,根据我的(显而易见的错误)思维将是11

该函数如何得到13的结果？