关于斐波那契额的一个算法的时间复杂度的问题

作者：炫彩十字绣I_775 | 来源：互联网 | 2023-10-10 17:06

intj1,i0;for(intn0;i<m;i++){jj+i;ij-i;}returnj;我在《算法基础》中看到这个算

int j=1,i=0;
for(int n=0;i j = j + i;
i = j - i;
}
return j;

我在《算法基础》中看到这个算法。
书中说明这个算法的时间复杂度是O(n^2);
请各位高手指点一下为什么是O(n^2)

16 个解决方案

#1

应该是O(n)吧!应该再完整一点,另外没看出来变量n的作用!

#2

一重循环走到底，肯定是线性的时间复杂度，不会是O(n^2)
lz看错了吧~

#3

lz贴的代码是不是有错？

#4

关键在于循环体中对循环变量i作了修改，所以问题就有点儿复杂，需要再仔细分析一下。

#5

想错了，没有什么埋伏，就只是道错题

#6

#7

JAVA源代码：
/**
* 斐波那契数列 --- 经典
* @param n
* @return
*/
public int fibonacci(int n){
int j=0,i=1;

for(int k=0;k j = i + j;
i = j - i;
}
return j;
}

说明部分：

斐波那契额公式是
f(n) = f(n-1) + f(n-2)
f(n) = j; f(n-1) = i;

书上说 j=j+i和i=j-i 分别为 O(n)和O(n-1）
而不是O(1)
所以整个循环的时间复杂度就是O(n^2)了。

书上是这么说的。
但是问题是为什么 j=j+i和i=j-i 分别为 O(n)和O(n-1）
书上没有说明。

请教各位高手，小弟不胜感激。

#8

O(n)，肯定是O（n）嘛

#9

书上应该是把j=j+i,i=j-i当大数运算了吧，这样当然算是O(n)。把int替换成大数类型就可以计算很大的斐波那契数了。

#10

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

#11

为什么我算的O（log(n)）

#12

O(n)，加一个计数就可以算出来了。



#include 

using namespace std;

int fibonacci(int n)

{

	int j = 0, i = 1;

	int cnt = 0;

	for(int k=0;k 
	{

		j = i + j;

		i = j - i;

		cnt++;

	}

	cout<
	return j;

}

int main()

{

	fibonacci(10);

	return 0;

}

#13

路过。

#14

不是吧，好像是（5/3）n次幂

#15

汗....
未递归单循环
看出花来了....

#16

学习了。

推荐阅读

string
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
include
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
string
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
string
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
sum
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
include
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
include
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
string
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
sum
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
get
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
string
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
copy
输出1000内能被3整除且个位数为6的所有整数的程序填充

本文介绍了一个程序，可以输出1000内能被3整除且个位数为6的所有整数。程序使用了循环和条件判断语句来筛选符合条件的整数，并将其输出。 ... [详细]

蜡笔小新 2023-12-13 16:30:11
string
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新 2023-12-13 22:09:56
string
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
string
JVM 学习总结（三）——对象存活判定算法的两种实现

本文介绍了垃圾收集器在回收堆内存前确定对象存活的两种算法：引用计数算法和可达性分析算法。引用计数算法通过计数器判定对象是否存活，虽然简单高效，但无法解决循环引用的问题；可达性分析算法通过判断对象是否可达来确定存活对象，是主流的Java虚拟机内存管理算法。 ... [详细]

蜡笔小新 2023-12-13 18:59:46

炫彩十字绣I_775

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章