二分递归：数组求和（java实现）

二分递归：数组求和

1、代码实现： 

代码语言：javascript复制

package com.mooc.arithmetic;
/**
 * 二分递归：数组求和
 * @author com
 *分治思想：先把问题分解成两个子问题，再把两个子问题递归地分解成最简单的子问题，
 *		     最后再把所有的子问题合并
 */
public class BinarySum {
	
	static int A[] = {15,20,1,5,7,12,47,-3,0,99,18};
	public static void main(String[] args) {
		BinarySum BS = new BinarySum();
		int sum = BS.sum(A, 0, A.length-1);
		System.out.println(sum);
	}
	public int sum(int A[],int lo,int hi) {
		if(lo == hi) return A[lo];				//出口判断
		int mid = (lo hi)>>1;					//中值
		return sum(A,lo,mid) sum(A,mid 1,hi);	//递推方程
	}
}

2、运行结果： 

3、算法复杂度：o(n) 

递归 数组

0 人点赞