递归－求幂

计算幂，n^m，其中n为底数，m为幂
当m取值比较大时如果采用m个n相乘的办法，计算显得冗长。

可以采用以下方法重新组织算法：

n^m == n^((m/2) * 2)
n^m == (n^(m/2))^2

假设如果可以求得temp = n^(m/2),则n^m = temp * temp
这里采用了递归的做法，将n^m问题转换成为n^(m/2)的问题,将近减少了一半运算量。

特殊情况是m不是偶数的情况，这种状况下：

temp = n^(m/2)
n^m = temp * temp * n （多乘一次就可以解决这个问题）

时间代价从原来的O(m) 变成了 O(log m)，再这种情况下递归可以提高运行效率。

代码如下：

class Power {
	public static void main(String[] args) {
		for(int i=0; i< 11; i++) {
			System.out.print(power(3,i) + " ");
		}
		System.out.println();
	}

	private static long power(int n, int m) {
		assert m >= 0;
		if(m == 0) return 1;
		if(m == 1) return n;
		long temp = power(n,m/2);
		return m%2 == 0? temp * temp: temp * temp * n;
	}
}

 

评论

1 楼 wpf523 2012-04-11  

不错，的算法