斐波那契数列的时间复杂度

Question

如题所述

Answer 1

斐波那契数列时间复杂度如下：

当参数为n时，时间复杂度为f(n)=f(n-1)+f(n-2)。

当n为6时，树的高度为5即h=n-1的高度，共有15个节点即2^(h-1)-1个。

时间复杂度为O(2^n)=f(2^n-1)-1。

空间复杂度为O(n)=f(n-1)。

拓展知识：

在数学当中，由斐波那契数字构成的序列，被称为斐波那契数列。该数列中的每一个数字等于排在它前面的两个数字之和。

斐波那契数列，又称黄金分割数列，因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=1，F(1)=1,F(n)=F(n-1)+F(n-2)（n≥2，n∈N*）。

1202年，斐波那契在《计算之书》中提出了斐波那契数列。根据该数列可折叠出斐波那契蜗牛；绘制出斐波那契螺旋线等。此外，在现代物理、准晶体结构、化学等领域，该数列均有直接应用；为此，美国数学会从1963年起出版了一份名为《斐波那契数列季刊》的数学杂志，以专门刊载相关研究成果。

斐波那契数列的定义者，是意大利数学家莱昂纳多·斐波那契，生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的莱昂纳多”。1202年，他撰写了《算盘全书》一书。

他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点于阿尔及利亚地区，莱昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。另外斐波那契还在计算机C语言程序题中应用广泛。