首页 > 代码库 > 【算法数据结构Java实现】递归的简单剖析及时间复杂度计算

【算法数据结构Java实现】递归的简单剖析及时间复杂度计算

1.理解

            对于递归函数的理解,我觉得是比较重要的,因为很多大神能把递归函数用的惟妙惟肖,不光是他们的编程功力高深,更主要是能理解这个算法。比较直白的理解是,如果一个事件的逻辑可以表示成,f(x)=nf(x-1)+o(x)形式,那么就可以用递归的思路来实现。

编写递归逻辑的时候要知道如下法则:
1.要有基准
  比如说,f(x)=f(x-1)+1,如果不加入基准,f(0)的值是多少,那么函数会无限执行下去,没有意义
2.不断推进
  也就是f(x)=f(x-1)或是f(x)=f(x/n)之类的
          
           
 当然每个递归函数会有一个比较神奇的步骤,就是回溯步骤,比方说:
    
  fact(3) ----- fact(2) ----- fact(1) ------ fact(2) -----fact(3) 
    ------------------------------>  ------------------------------> 
                递归                            回溯 

2.实例实现


      求 的计算和f(x)=0,首先列出公式f(x)=f(x-1)+x/(4**x)     (两个**表示次方,python用惯了),得到下面的代码
public class Recursion {
     public static void main(String args[]){
   
    	  System.out.print(f(2));
  	 }
	   public static double f(int x){
		   if (x==0){
			   return 0;
		   }
		   else{
			   return f(x-1)+x/Math.pow(4,x);
		   }
	   }
}

结果是:f(2)=0.375,验证正确


3.时间复杂度计算


        以上题为例,将f(x)=f(x-1)+x/(4**x)展开,


将f(x)乘以4相减,得,设4的x方等于k,则原式时间复杂度,log以4为底。





参考:http://blog.csdn.net/budapest/article/details/6367973


/********************************

* 本文来自博客  “李博Garvin“

* 转载请标明出处:http://blog.csdn.net/buptgshengod

******************************************/




【算法数据结构Java实现】递归的简单剖析及时间复杂度计算