`
naouguhtaeyeti
  • 浏览: 20578 次
文章分类
社区版块
存档分类
最新评论

f(n) = f(n-1) + f(n-2) 实现(递归与非递归运行时间比较)

    博客分类:
  • java
阅读更多
Fibonacci 算法递归实现与非递归实现时间比较:

public class Question1 {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long start,end;
		int n=50;
		start = System.currentTimeMillis();
		getWays(n);
		end = System.currentTimeMillis();
		System.out.println("Non recursive cost time :"+ (end-start));
		
		start = System.currentTimeMillis();
		getWays_1(n);
		end = System.currentTimeMillis();
		System.out.println("recursive cost time :"+ (end-start));
	
	}
	
	public static long getWays(int n){
		// TODO Auto-generated method stub
		long[] f = new long[n+1];
		f[1]=1;
		f[2]=2;
		for(int i=3;i<=n;i++){
			f[i]=f[i-1]+f[i-2];
		}		
		return f[n];
	}
	
	public static long getWays_1(int n){
		if(n==1){
			return 1;
		}
		if(n==2){
			return 2;
		}
		return getWays_1(n-1)+ getWays_1(n-2);
	}
}



运行结果:
Non recursive cost time :0
recursive cost time :99093
分享到:
评论

相关推荐

    菲波拉契数列的递归与非递归算法

    \[ F(n) = \begin{cases} 1 & n = 1 \\ 1 & n = 2 \\ F(n-1) + F(n-2) & n &gt; 2 \end{cases} \] 其中 \(F(n)\) 表示数列中的第 \(n\) 个数。数列的前几项为:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... #### 三、...

    实验1-递归算法1

    Fibonacci数列是一个典型的递归问题,它的定义是:F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2),对于n &gt; 1。递归实现Fibonacci数列的方法如下: ```python def fibonacci_recursive(n): if n &lt;= 0: return 0 ...

    算法时间复杂度分析中递归方程求解方法综述

    形如`f(n) = a_1f(n-1) + a_2f(n-2) + \cdots + a_kf(n-k) + g(n)`的递归方程,其解可以分为两部分:对应齐次方程的通解和非齐次方程的特解。特解的具体形式取决于`g(n)`的类型。 ### 递推方法求解递归方程 递推法...

    斐波那契非递归 C语言源码 大数加法

    斐波那契数列是一种经典的数学序列,定义如下:F(0) = 0, F(1) = 1, 对于 n &gt; 1, F(n) = F(n-1) + F(n-2)。这个序列在计算机科学中有着广泛的应用,包括算法设计、动态规划、数据结构优化等。在C语言中实现斐波那契...

    class3-Fibonacci.rar_Fibonacci_Fibonacci+c++_fibonacci数列

    F(n) = F(n-1) + F(n-2) (n &gt; 1) 这个数列在计算机科学中有广泛的应用,特别是在算法设计、数据结构、计算复杂性理论以及各种实际问题的求解中。 在这个“class3-Fibonacci.rar”压缩包中,包含了一个名为...

    JAVA递归与非递归实现斐波那契数列

    用数学公式表示就是 F(0) = 0,F(1) = 1,对于 n &gt;= 2,F(n) = F(n-1) + F(n-2)。 在Java中,斐波那契数列可以用递归和非递归两种方法来实现。 1. **递归实现**: 递归实现是最直观的方式,它通过函数自身调用来...

    第二章分治与递归(全)

    斐波那契数列的定义是第 n 个数等于前两个数的和,即 F(n) = F(n-1) + F(n-2),其中 F(0) = 0 和 F(1) = 1。递归实现如下: ```c int fibonacci(int n) { if (n &lt;= 1) { return n; // 基本情况 } return ...

    实验一 斐波那契数列的实现算法及分析.docx

    数学表示为:F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n &gt;= 2)。这个数列在算法设计、数据结构、计算复杂性等领域都有广泛的应用。 在给定的文件中,提到了斐波那契数列的两种常见实现方法:递归和非递归...

    集合划分问题 java实现

    f(n, m) = f(n-1, m-1) + m*f(n-1, m) 在 Java 中,可以使用递归函数来实现该公式,如下所示: ```java public class Partition { public int Partition(int n, int m) { if (n == 0 || m == 0) return 0; if (n...

    广义表操作的递归汇总PPT学习教案.pptx

    斐波那契数列是一个经典的递归问题,其定义是`F(n) = F(n-1) + F(n-2)`。这个例子中,既展示了递归解法,也给出了非递归(迭代)解法。非递归解法通常在效率上优于递归,因为它避免了重复计算和过多的函数调用。 ...

    实验1斐波那契数列的实现算法以及分析.pdf

    递归函数基于斐波那契数列的定义,直接利用递归关系计算`Fn`,即`F_n = F_{n-1} + F_{n-2}`,当`n=0`或`n=1`时返回1。非递归函数`Fib_ite`采用迭代的方式,通过循环累加前两个数来获取当前项,避免了递归带来的重复...

    Fibonacci数列函数

    用数学公式表示就是 F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2),对于 n &gt; 2。 在编程中,我们通常会用两种方式来实现斐波那契数列:递归和非递归(迭代)。 1. **递归实现**: 递归方法基于斐波那契数列的定义...

    用母函数理论分析递归算法的时间复杂度

    斐波那契数列的递归关系是F(n) = F(n-1) + F(n-2),我们可以构建一个生成函数F(x) = ΣF(n)x^n,通过求解该生成函数,可以发现斐波那契数列的生成函数具有特定的奇偶性质,即F(2n)和F(2n+1)都满足一个特定的递推关系...

    递归形式与非递归形式的斐波那契数列的用法分析

    用数学公式表示为:F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2),其中n大于2。 **递归形式的斐波那契数列** 在递归形式的实现中,斐波那契数列的计算是通过函数调用自身来完成的。如上述代码所示,`...

    算法导论答案 经典

    - **5.3-1**:了解期望运行时间的概念。 - **5.3-2**:探讨如何计算算法的期望运行时间。 - **5.3-3**:研究随机化算法的期望运行时间。 - **5.3-4**:理解期望运行时间与最坏情况运行时间的区别。 ### 第6章 - 堆...

    实验一斐波那契数列的实现算法及分析.pdf

    通过比较非递归和递归算法的运行时间,我们可以看出非递归(迭代)方法在效率上通常优于递归方法,尤其是当n值较大时,递归方法可能会因为大量的重复计算而导致显著的性能下降。在实际编程中,如果对时间复杂度有...

    算法复杂度计算方法

    - 如果存在一个函数f(n),使得当n趋向无穷大时,算法的执行时间T(n)与f(n)的比值趋于一个非零常数,则称f(n)为算法的时间复杂度,记作T(n) = O(f(n))。 - **示例**: - T(n) = n² + 3n + 4 和 T(n) = 4n² + 2n +...

    C语言经典试题

    return f(m-1, n) + f(m-1, n-1); // 填充部分 } ``` #### 二、编程题 **知识点7:求素数** - **Eratosthenes 筛法**:这是一种高效的求解一定范围内所有素数的方法。通过标记非素数的方式,快速筛选出所有素数...

    计算机算法基础

    \[T(n) = T(2^k) = 2^k \cdot g(n) + 2^{k-1} \cdot f(2) + 2^{k-2} \cdot f(2^2) + \cdots + 2^0 \cdot f(2^k)\] 设\(g(n) = a\), \(f(n) = bn\),其中\(a\), \(b\)为正常数。那么, \[T(n) = 2^k \cdot a + b(2^{...

    青蛙爬楼梯(C++源码)

    `f(n) = f(n-1) + f(n-2)` 这里的f(n)代表跳上n级台阶的总方法数。然而,递归解法的时间复杂度较高,因为它会重复计算很多子问题,不适合处理大值的n。 接下来,我们转向更优的动态规划方法。动态规划是一种将问题...

Global site tag (gtag.js) - Google Analytics