相关疑难解决方法(0)

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

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

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

以下是我编写的用于计算Fibonacci序列中的值的方法:

def fib(n)

    if n == 0
        return 0
    end
    if n == 1
        return 1
    end

    if n >= 2
        return fib(n-1) + (fib(n-2))
    end

end

它工作起来n = 14,但之后我得到一条消息说该程序花了太长时间才响应(我正在使用repl.it).任何人都知道为什么会这样吗？