1.5迭代与递归

1、数组求和：迭代

实现：逐一取出，累加之

int SumI(int A[], int n){ int sum=0;//o(1) for(int i=0;i<n;i++){//o(n) sum+=A[i];}//o(1) return sum; }

2、数组求和：线性递归

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

T(n)=o(n)

3、数组倒置

A[0,n]，子区间A[lo,hi] 接口：

void reverse(int* A, int lo, int hi);

递归版：

if(lo<hi){swap(A[lo], A[hi]);reverse(A, lo+1, hi+1);}

迭代版： while(lo<hi){swap(A[lo++], A[hi–]);}

4、数组求和：二分递归

sum(int A[], int lo, int hi){ if(lo==hi) return A[lo]; int mi=(lo+hi)>>1; return sum(A,lo,mi)+sum(A,mi+1,hi) }

T(n)=o(n)

5、Max2：迭代

从数组区间A[lo,hi]中找出最大的数A[x1]>=A[x2]

方法1

void max2(int A[], int lo, int hi, int & x1, int & x2){ for(x1=lo,int i=lo+1;i<hi;i++){ if(A[x1]<A[i]) x1=i; } for(x2=lo,int i=lo+1;i<x1;i++){//扫描x1前的 if(A[x2]<A[i]) x2=i; } for(nt i=x1+1;i<hi;i++){//扫描x1后的 if(A[x2]<A[i]) x2=i; } }

比较总数2n-3

方法2：

void(int A[], int lo, int hi, int & x1, int & x2){ if(A[x1=lo]<A[x2=lo+1]){swap(x1,x2);} for(int i=lo+2;i<hi;i++){ if(A[x2]<A[i]){ if(A[x1]<A[x2=i]swap(x1,x2);) } } }

最好时：n-1 最坏时：2n-3

方法3：递归+分治

void max2(int A[], int lo, int hi, int & x1, int & x2){ if(lo+2==hi){if(A[x1=lo]<A[x2=lo+1])swap(x1,x2);}//双人对局 if(lo+3==hi){ if(A[x1=lo]<A[x2=lo+1]){swap(x1,x2);}//前两人对局 if(A[x2]<A[i+2]){ if(A[x1]<A[x2=i+2]){swap(x1,x2);//加入第三者对局 } } } int mi=(lo+hi)/2; int x1L,x2R;max2(A,lo,mi,x1L,x2L);//东部入围赛 int x1R,X2R;max2(A,mi,hi,x1R,x2R);//西部入围赛 if(A[x1L]>A[x1R]){//冠军赛 x1=x1L;x2=(A[x2L]>A[x1R])?x2L:x1R;//亚军赛 }else{ x1=x1R;x2=(A[x1L]>A[x2R])?x1L:x2R; } }