算法求解-数组求和

算法求解-数组求和

二分递归

算法：分而治之

sum(int A[], int lo,int hi) //区间范围，入口形式为sum(A,0,n-1) { if(lo==hi) return A[lo]; int mi=(lo+hi)/2; return sum(A,lo,mi)+sum(A,mi+1,hi); }

T(n)=各层递归实列所需时间和 $$=O(1)\ast (2^0+2^1+2^2+2^3+\cdots +2^{(}lo{g}_{2}n))$$

$$=O(1)\ast (2^{(}lo{g}_{2}n)-1)$$

$$=O(n)$$

递归基：sum(A,lo,lo)

递推方程 $$T(n)=2\ast T(n/2)+O(1)$$

$$T(1)=O(1)$$

线性递归

sum(int A[],int n) { return (n<1) ? 0 : sum(A,n-1) +A[n-1]; }

时间复杂度：

单个递归实列自身只需 O（1） $$T(n)=O(1)\ast (n+1)=O(n)$$ 递归基：sum(A,0)

递推方程 $$T(n)=T(n-1)+O(1)$$

$$T(0)=O(1)$$

求解： $$T(n)-n=T(n-1)-(n-1)=\cdots$$

$$=T(2)-2$$

$$=T(1)-1$$

$$=T(0)$$

移项： $$T(n)=O(1)+n=O(n)$$