- 浏览: 20633 次
文章分类
- 全部博客 (17)
- Struts (0)
- Servlet (1)
- Interview (1)
- Shell (1)
- java (5)
- Linux (0)
- ACM (1)
- 程序员 (0)
- Sprint (0)
- Spring (1)
- WEB (0)
- 学习方法 (0)
- JSP (0)
- other problems Collecting (0)
- Hibernate (0)
- Thread (1)
- AWT (0)
- 生活哲理 (0)
- IT 人物 (1)
- IT knowledge (0)
- 版本管理软件 (1)
- 深入java (0)
- Oracle (0)
- Activity (0)
- GUI (1)
- English (0)
- 网络编程 (0)
- Practice (0)
- 项目实践 (0)
- 金融 (0)
- 面试 (1)
- 新知识 (0)
- 温故旧知识 (0)
- 账户管理 (0)
- IT 警言 (1)
- 学习 (0)
- Strus (0)
- 问题 (0)
- 武术 (0)
- 经济 (0)
- 项目 (0)
- 项目构建工具 (0)
- 每天学习 (0)
- 面试题 (0)
- 编程实践-解题(Solution) (0)
- 领悟 (0)
- log (0)
- 编程 (0)
- 算法 (0)
- Java 学习 (0)
- 好好学习,天天进步-每一天的时间都一样,但是可以有不同的价值 (0)
- 幸福 (0)
- hibernate 实践笔记 (0)
- Spring 实践笔记 (0)
- 设计模式系列 (0)
- acm 练习总结 (0)
- JVM 学习 (0)
- 目标 (0)
- 人生准则 (0)
- 开源 框架 (0)
- AOP 学习系列 (0)
- java 网络编程 (0)
- 源码学习 (0)
- ClassLoader (0)
- 动态代理 (0)
- 开源项目 (0)
- 编码 (0)
- 我的生活领悟 (0)
- 事务安排 (0)
- 电话面试 (0)
- 学习笔记 (0)
- 开源软件学习 (0)
- PLSQL (0)
- 面试准备 (0)
- 日记 (0)
- 离职找工作日记 (0)
- hibernate 学习 (0)
- tomcat 源码学习 (0)
- 成长日记 (0)
- 算法学习-从概念开始一点一点的学习 (0)
- Spring MVC (0)
- 进步的人生 (0)
- 一定要坚定 (0)
- 程序员的实力 (0)
- 学习进步-日知其所亡,月无忘其所能,学无先后,快慢,达者为先,通者为先。 (0)
- 日知其所亡,月无忘其所能,学无先后,快慢,达者为先,通者为上 (0)
- 公积金 (0)
- test (0)
Fibonacci 算法递归实现与非递归实现时间比较:
运行结果:
Non recursive cost time :0
recursive cost time :99093
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
发表评论
-
java 内置的比较器
2012-06-28 12:04 972在java 里,有一些内置的比较器,比如CaseInsensi ... -
java 每日学习
2012-06-22 11:57 0今天看了简单工厂模式与工厂方法模式,然后看的过程中碰到一些问题 ... -
java RTTI- runtime type information (think in java )
2012-06-18 23:53 0Class 类 equals 方法比较与 instanceof ... -
ant 使用
2012-05-30 00:39 0ant : a neat tool 1.下载 ant ht ... -
java multithread
2012-05-24 13:24 0java 多线程 使用condition 来控制协调。 区别 ... -
java Queue
2012-05-24 10:39 0java Collection Queue 的实现及 Pri ... -
网络连接例子
2012-05-20 20:39 0来自java 学习室 -
java io 集合 笔试题
2012-05-18 18:44 0摩根笔试题: import java.io.Buffere ... -
学习 JAVA IO
2012-05-17 00:29 0http://www.java3z.com/cwbwebhom ... -
java Runtime
2012-05-16 22:47 0Java垃圾回收时需要用到Runtime(这是一个单例模式), ... -
装饰模式
2012-05-16 12:19 0问题: 根据问题来学习,并学习如何理解讲解问题更透彻明白,及学 ... -
java io 设计
2012-05-15 22:46 0转载自: http://www.blogjav ... -
垃圾回收
2012-05-14 21:34 0参考垃圾回收电子书: ... -
java 基础
2012-05-03 23:50 737读 《研读设计模式》 简单工厂的优缺点: 帮助封装 简单工厂 ... -
Java 集合
2012-04-23 12:04 942今天在做如何从两个数组中取出相同的元素时碰到了一个问题,想知道 ... -
java 多态的情况
2012-04-15 23:34 1102参考 http://topic.csdn.net/u/2012 ...
相关推荐
\[ F(n) = \begin{cases} 1 & n = 1 \\ 1 & n = 2 \\ F(n-1) + F(n-2) & n > 2 \end{cases} \] 其中 \(F(n)\) 表示数列中的第 \(n\) 个数。数列的前几项为:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... #### 三、...
Fibonacci数列是一个典型的递归问题,它的定义是:F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2),对于n > 1。递归实现Fibonacci数列的方法如下: ```python def fibonacci_recursive(n): if n <= 0: return 0 ...
形如`f(n) = a_1f(n-1) + a_2f(n-2) + \cdots + a_kf(n-k) + g(n)`的递归方程,其解可以分为两部分:对应齐次方程的通解和非齐次方程的特解。特解的具体形式取决于`g(n)`的类型。 ### 递推方法求解递归方程 递推法...
斐波那契数列是一种经典的数学序列,定义如下:F(0) = 0, F(1) = 1, 对于 n > 1, F(n) = F(n-1) + F(n-2)。这个序列在计算机科学中有着广泛的应用,包括算法设计、动态规划、数据结构优化等。在C语言中实现斐波那契...
F(n) = F(n-1) + F(n-2) (n > 1) 这个数列在计算机科学中有广泛的应用,特别是在算法设计、数据结构、计算复杂性理论以及各种实际问题的求解中。 在这个“class3-Fibonacci.rar”压缩包中,包含了一个名为...
用数学公式表示就是 F(0) = 0,F(1) = 1,对于 n >= 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 <= 1) { return n; // 基本情况 } return ...
数学表示为:F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2)。这个数列在算法设计、数据结构、计算复杂性等领域都有广泛的应用。 在给定的文件中,提到了斐波那契数列的两种常见实现方法:递归和非递归...
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...
斐波那契数列是一个经典的递归问题,其定义是`F(n) = F(n-1) + F(n-2)`。这个例子中,既展示了递归解法,也给出了非递归(迭代)解法。非递归解法通常在效率上优于递归,因为它避免了重复计算和过多的函数调用。 ...
递归函数基于斐波那契数列的定义,直接利用递归关系计算`Fn`,即`F_n = F_{n-1} + F_{n-2}`,当`n=0`或`n=1`时返回1。非递归函数`Fib_ite`采用迭代的方式,通过循环累加前两个数来获取当前项,避免了递归带来的重复...
用数学公式表示就是 F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2),对于 n > 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章 - 堆...
通过比较非递归和递归算法的运行时间,我们可以看出非递归(迭代)方法在效率上通常优于递归方法,尤其是当n值较大时,递归方法可能会因为大量的重复计算而导致显著的性能下降。在实际编程中,如果对时间复杂度有...
- 如果存在一个函数f(n),使得当n趋向无穷大时,算法的执行时间T(n)与f(n)的比值趋于一个非零常数,则称f(n)为算法的时间复杂度,记作T(n) = O(f(n))。 - **示例**: - T(n) = n² + 3n + 4 和 T(n) = 4n² + 2n +...
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^{...
`f(n) = f(n-1) + f(n-2)` 这里的f(n)代表跳上n级台阶的总方法数。然而,递归解法的时间复杂度较高,因为它会重复计算很多子问题,不适合处理大值的n。 接下来,我们转向更优的动态规划方法。动态规划是一种将问题...