# time-complexity - notation是什么 - leetcode fibonacci

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

``````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斐波纳契数封闭表达式

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

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

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

`T(n) = T(n-1) + T(n-2) + O(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` `)`

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

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

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

``````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）

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];
}
``````

``````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;
}
``````

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

`2^n [ O(2^n) ]`