斐波那契数的时间复杂度、空间复杂度详解

您所在的位置：网站首页 › 斐波那契数列的递归算法的时间复杂度 › 斐波那契数的时间复杂度、空间复杂度详解

斐波那契数的时间复杂度、空间复杂度详解

#斐波那契数的时间复杂度、空间复杂度详解| 来源: 网络整理| 查看: 265

斐波那契数列： f(n)=f(n-1)+f(n-2)(n>2) f(0)=1;f(1)=1; 即有名的兔子繁衍问题在本篇文章我将会给出三种解法

方法一：递归 static int f1(int i) { if (i == 1 || i == 2) return 1; else return f1(i - 1) + f1(i - 2); }

1.时间复杂度 O(2^n) 首先可以根据函数递归执行顺序画出下图的二叉树结构（假设求第五个斐波那契数）

image.png

2.空间复杂度 O(1)

image.png

①-③：调用Fib(5),首先需调用Fib(4),Fib(4)要先调用Fib(3)，逐步调用直至返回Fib(2)的值1，Fib执行结束，所创建空间销毁。此时Fib(5)、Fib(4)、Fib(3)均未调用结束，程序共占用4个函数栈帧空间。

④-⑨：Fib(2)执行结束，接下来调用Fib(1)，创建一个函数栈帧空间，调用结束返回1后，该空间销毁，此时可得到Fib(3)=2，通过第⑦步返回Fib(3)的值，第⑧步同样创建空间再次调用Fib(2)，调用结束销毁空间，此时可得到Fib(4)=3，通过第⑨步返回Fib(4)的值，此过程最大占用4个函数栈帧空间。

⑩-···：最后和上面一样，调用Fib(3)，将返回值传给Fib(5)的模块，最终得到Fib(5)=5。

整个程序执行过程中，最多占用4个函数栈帧空间的大小，设一个函数栈帧空间为C 因此可得知当n=5时，该程序空间复杂度为O(4C)=>O(1) 当求第n个斐波那契数时，程序空间复杂度为O(n-1)C (n是常数)=>O(1)

方法二：循环 image.png static int f2(int n) { int count = 1; int Fn_1 = 1; int Fn_2 = 1; while (n > 2) { Fn_2 = Fn_1; Fn_1 = count; count = Fn_1 + Fn_2; n--; } return count; }

1.时间复杂度 O(n) 程序中循环了n-2次，时间复杂度为O(n-2),保留最高阶时间复杂度为O(n)

2.空间复杂度 O(1) 该程序中创建了3个变量，即创建了3个内存空间，空间复杂度为O(3)即O(1)

方法三：尾递归 image.png int fib(int n) { int pre = 1; int ppre = 0; int ret = 0; for (int i = 1; i

【本文地址】

斐波那契数的时间复杂度、空间复杂度详解

斐波那契数的时间复杂度、空间复杂度详解

今日新闻

推荐新闻