time-complexity - notation是什么 - leetcode fibonacci




斐波那契数列的计算复杂性 (8)

麻省理工学院对这个具体问题进行了很好的讨论。 在第5页中,他们指出,如果您假设一个加法需要一个计算单位,计算Fib(N)所需的时间与Fib(N)的结果非常接近。

因此,您可以直接跳至斐波那契数列的非常接近的近似值:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

并且说,因此,朴素算法的最坏情况表现是

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS:如果您想了解更多信息,可以在维基百科讨论关于第N斐波纳契数封闭表达式

我理解Big-O符号,但我不知道如何计算它的许多功能。 特别是,我一直在试图找出斐波那契序列天真版本的计算复杂性:

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

斐波纳契数列的计算复杂度是多少?它是如何计算的?



它的下限为2^(n/2) ,上限为2 ^ n(如其他评论所述)。 这个递归实现的一个有趣的事实是它具有Fib(n)本身的紧的渐近界。 这些事实可以概括为:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

如果您愿意,可以使用其封闭形式进一步缩小紧密边界。


您可以对时间函数进行建模,以计算Fib(n)为计算Fib(n-1)加上计算Fib(n-2)的时间加上它们加在一起的时间( O(1) )的时间之和。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

你解决这个重复关系(例如使用生成函数),你会最终得到答案。

或者,您可以绘制递归树,该树具有深度n并直观地指出该函数渐近地为O(2 n ) 。 然后你可以通过归纳证明你的猜想。

基数: n = 1是显而易见的

因此,假设T(n-1) = O(2 n-1 )

T(n) = T(n-1) + T(n-2) + O(1) 等于

T(n) = O(2 n-1 ) + O(2 n-2 ) + O(1) = O(2 n )

但是,正如评论所指出的那样,这不是一个严格的限制。 关于这个函数的一个有趣的事实是T(n)与Fib(n)的值渐近地相同 ,因为它们都被定义为

f(n) = f(n-1) + f(n-2)

递归树的叶子将始终返回1. Fib(n)的值是递归树中叶子返回的所有值的和,等于树叶的数量。 由于每一片叶子都将采用O(1)进行计算,因此T(n)等于Fib(n) x O(1) 。 因此,这个函数的紧束缚是斐波那契数列本身( θ(1.6 n ) )。 你可以通过使用上面提到的生成函数来找出这个紧密的界限。


我同意pgaur和rickerbh,递归斐波那契的复杂性是O(2 ^ n)。

我以相当简单的方式得出了相同的结论,但我相信仍然是有效的推理。

首先,计算第N个斐波纳契数时,要计算多少次递归斐波那契函数(从现在开始)(F())。 如果在序列0到n中每个数字被调用一次,那么我们有O(n),如果每个数字被调用n次,那么我们得到O(n * n)或O(n ^ 2),等等。

所以,当F()被调用到n时,对于0和n-1之间的给定数字调用F()的次数会随着接近0而增长。

作为第一印象,在我看来,如果我们用一种可视化的方式来描述它,每次绘制一个单位F()被称为一个给定的数字,弄湿得到一种金字塔形状(也就是说,如果我们将单位水平居中)。 像这样的东西:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

现在的问题是,随着n的增长,这个金字塔的基础有多快扩大?

我们来看一个真实的案例,例如F(6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

我们看到F(0)被调用32次,这是2 ^ 5,对于这个示例情况是2 ^(n-1)。

现在,我们想知道F(x)被调用了多少次,我们可以看到F(0)被调用的次数只是其中的一部分。

如果我们将所有*从F(6)到F(2)的所有行都精神地移动到F(1)行,我们可以看到F(1)和F(0)行的长度现在相等。 这意味着,当n = 6时F()被调用的总次数是2x32 = 64 = 2 ^ 6。

现在,就复杂性而言:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)

斐波那契的天真递归版本由于重复计算而呈指数形式:

在你计算的根源上:

F(n)取决于F(n-1)和F(n-2)

F(n-1)再次依赖于F(n-2),F(n-3)

F(n-2)再次依赖于F(n-3),F(n-4)

那么你在每个级别都有2个递归调用,这会浪费计算中的大量数据,时间函数将如下所示:

T(n)= T(n-1)+ T(n-2)+ C,其中C恒定

T(n-1)= T(n-2)+ T(n-3)> T(n-2)

T(n)> 2 * T(n-2)

...

T(n)> 2 ^(n / 2)* T(1)= O(2 ^(n / 2))

这只是一个下限,为了您的分析的目的应该足够了,但实时函数是相同斐波那契公式的一个常数因子,并且已知封闭形式是黄金比率的指数。

另外,你可以使用如下的动态编程来找到斐波那契的优化版本:

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

这是优化的,只做n步,但也是指数。

成本函数是从输入大小到解决问题的步骤数量定义的。 当你看到斐波那契的动态版本( n个步骤来计算表格)或者知道数字是否为素数的最简单算法( sqrt(n)来分析数字的有效除数时)。 你可能会认为这些算法是O(n)O(sqrt(n)),但是由于以下原因,这是不正确的:算法的输入是一个数字: n ,使用二进制符号输入大小整数nlog2(n)然后做一个变量的变化

m = log2(n) // your real input size

让我们根据输入大小找出步数

m = log2(n)
2^m = 2^log2(n) = n

那么作为输入大小的函数,算法的成本是:

T(m) = n steps = 2^m steps

这就是为什么成本是指数的原因。


这表现得更好:

unsigned int Fib(unsigned int n)
{
    // first Fibonaci number is Fib(0)
    // second one is Fib(1) and so on

    // unsigned int m;  // m + current_n = original_n
    unsigned int a = 1; // Fib(m)
    unsigned int b = 0; // Fib(m-1)
    unsigned int c = 0; // Fib(m-2)

    while (n--)
    {
        c = b;
        b = a;
        a = b+c;
    }

    return a;
}

那么,据我所知这是O(2^n)因为在这个函数中只有递归需要相当长的时间(分而治之)。 我们看到,上面的函数将继续在树中,直到当叶到达F(n-(n-1))级时,即叶子接近F(1) 。 所以,当我们记下在树的每个深度遇到的时间复杂度时,总和系列是:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

2^n [ O(2^n) ]





fibonacci