递归算法优化

    那天闲来无聊，突然从网上看到一google面试题，比较有意思，于是整理了下先写下来，算法大概是这样的：
    T(0) = T(1) = 1;
    T(2) = 2;
    T(N) = T(N-1) + T(N-2) + T(N-3);
    算法前提不考虑溢出，于是我写下了最常规的递归算法：

public class Tribonacci {
    public static int method(int n) {
        if( 0 == n || 1 == n) {
            return 1;
        } else if( 2 == n) {
            return 2;
        } else {
            return method(n - 1) + method(n - 2) + method(n - 3);
        }
    }
}

    但是仔细琢磨了下，当n >= 3 事， 条件进入最后的else,这里其实进行了多次递归,其中 在递归n-1的时候其实已经计算出了n-2、n-3, 所以这个算发，很显然重复计算了后便的method(n-2)、method(n-3)，所以这里可以在计算method(n-1)的时候记住n-2、与n-3的值，百般思索后写出了如下的程序：

public class Tribonacci {
    public static int method2(int n) {
        if( n < 0) {
            return 0;
        }
        if( 0 == n || 1 == n ) {
            return 1;
        }
        if( 2 == n ) {
            return 2;
        }
        ReferenceInt mid = new ReferenceInt();
        ReferenceInt last = new ReferenceInt();
		
        int max_subset = sub_recursion( n, mid, last);
        return max_subset + mid.getValue() + last.getValue();
    }

    public static int sub_recursion(int n, ReferenceInt mid, ReferenceInt last) {
        if ( 3 == n ) {
            mid.setValue(1);
            last.setValue(1);
            return 2;
        } else {
            ReferenceInt temp = new ReferenceInt();
            //这里做了参数移位，原来的last变为n-1的mid, 启用新的变量带出n-1的last
            mid.setValue(sub_recursion( n - 1, last, temp));
            return mid.getValue() + last.getValue() + temp.getValue();
        }
    }

    /**
     * 由于Java讨厌的自动封包机制，这里自己定义一个int的包装类型
     */
    class ReferenceInt {
        private int value;
	
	public ReferenceInt(int value) {
		this.value = value;
	}
	
	public ReferenceInt() {
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}
	
	public String toString() {
		return String.valueOf(this.value);
	}
    }
}

    算法的思想就是在计算n-1的时候，用参数带出n-2与n-3的值，去掉重复的计算，减少递归的次数，达到优化算法的效果，这里我简单说一下：
    T(N) = T(N-1) + T(N-2) + T(N-3);
          mas_sub    mid     last
    话说一个哥们，用list来缓存n-2 -> 0 之间的结果，随说有点吃内存，不过看起来比上边这个算法，好看多了，呵呵，都说是G内存的时代了，我一听乐了，不过也算是懒人有懒办法吧，贴出来大家看下：

public class Tribonacci {
    public static List<Integer> list = new ArrayList<Integer>();
    static {
        list.add(1);
        list.add(1);
        list.add(2);
    }
    public static int method3(int n) {
        if(n<list.size()){
            return list.get(n).intValue();
        }else{
            for(int i=list.size();i<=n;i++){
                list.add(method3(i - 1) + method3(i - 2) + method3(i - 3));
            }
            return method3(n);
        }
    }
}

呵呵，下边测试一下3个算法的性能吧：

public class Tribonacci {
    public static void main(String[] args) {
        final int TEST_NUMBER = 35;
        long start = System.currentTimeMillis();
        System.out.print(Tribonacci.method1(TEST_NUMBER));
        long end = System.currentTimeMillis();
	System.out.println("->method1(" + TEST_NUMBER + ") cost:" + (end-start) + "ms");
	start = System.currentTimeMillis();
        System.out.print(Tribonacci.method2(TEST_NUMBER));
        end = System.currentTimeMillis();
	System.out.println("->method2(" + TEST_NUMBER + ") cost:" + (end-start) + "ms");
	
        start = System.currentTimeMillis();
	System.out.print(Tribonacci.method3(TEST_NUMBER));
	end = System.currentTimeMillis();
	System.out.println("->method3(" + TEST_NUMBER + ") cost:" + (end-start) + "ms");
    }
}

1132436852->method1(35) cost:10468ms
1132436852->method2(35) cost:0ms
1132436852->method3(35) cost:0ms

评论

1 楼 linYuanSen 2012-09-05  

我自己的想法是，直接从头开始计算，到n为止。

public class Test {
	private static int iMax;//T(n-1)  max
	private static int iMid;//T(n-2)  mid
	private static int iLast;//T(n-3)  last
	
	public static void main(String[] args){
		System.out.println("T(0) " + fn(0) +"  T(1) " + fn(1) + "  T(2) " +fn(2));
		
		long start, end;
		 start = System.currentTimeMillis();  
	      System.out.println("fn36 : " + fn(35));  
	     end = System.currentTimeMillis();  
		System.out.println("pay times: " + (end - start) + "ms.");
		
	}
	
	
	public static int fn(int n){
		if(n < 3){
			return ((0==n || 1==n) ? 1 : 2);
		}else{
			init();
			int times = (int) Math.rint(n/3);//下面运算次数
			
			while(0 != times){
				iLast = iMax + iMid + iLast;//T(n-3) = T(n-4) + T(n-5) + T(n-6)
				iMid = iMax + iMid + iLast;//T(n-2) = T(n-4) + T(n-5) + T(n-3)
				iMax = iMax + iMid + iLast;//T(n-1) = T(n-4) + T(n-2) + T(n-3)
				times--;
			}
			
			int result = -1;
			if(0 == n % 3) result = iLast;
			if(1 == n % 3) result = iMid;
			if(2 == n % 3) result = iMax;
			
			return result;
		}
	}
	
	public static void init(){
		iMax = 2;
		iMid = 1;
		iLast = 1;
	}

}