数据结构与算法之迭代递归

刺骨的言语ヽ痛彻心扉 2023-07-14 05:25 1阅读 0赞

凡治众如治寡，分数是也。  
**数组求和：迭代**

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;  //O(1)
    }

**减而治之：**

> 将大问题划分为两个子问题：一个平凡问题和一个规模缩减并且形式与原问题形式相同的问题。分别解决这些子问题，然后合起来就解决原问题了。

//T(n) = O(1) * (n+1) = O(n)
    //这里的n+1是从main函数调用sum(A[],n)到sum(A[],1)调用sum(A[],0)共n+1次
    int sum(int A[], int n){
        
    	return
    		(n<1)?
    		 	0:sum(A,n-1) + A[n-1];

**线性递归**  
上述的算法的递归方程为：T(n) = T(n-1) + O(1) ; T(0) = O(1)  
求解：T(n) - n = T(n-1) - (n-1) = … =T(2) - 2 = T(1) - 1 =T(0) =O(1)  
所以T(n) = O(1)  
**数组倒置：**  
统一接口：void reverse(int\* A, int lo, int hi);

//递归法
    if(lo<hi)
    {
        swap(A[lo], A[hi]); reverse(A,lo+1,hi-1);}
    else
    	return ;

在这提供迭代法：（不过不是重点）

next:
    	if(lo < hi)
    		{
        swap(A[lo],A[hi]); lo++; hi--; goto next;}

迭代精简版：

while (lo < hi)  swap(A[lo++],A[hi--]);

**分而治之 Divide and Counte**r  
数组求和之二分递归：

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

复杂度分析  
O(1) \* (2^ 0 + 2^ 1 + 2^ 2 +… + 2^logn) = O(n)  
其实显然是一个几何级数：与末项的指数同阶（按照分层，每次分成俩，也就构成了以2为倍数的几何级数）[关于几何级数这篇博客有介绍][Link 1]

找数组中的前俩最大值：

//最好情况 是 n - 1
    //最坏情况 是 2n - 3
    void max2(int A[], int lo, int hi, int & x1,int & x2){
          // 1 < n = hi-lo
    	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);
    			
    		else continue;
    }

分治解法：  
分成两半，然后分别求出最大值和次大值；然后两者之间比较。

void max2(int A[], int lo, int hi, int & x1, int & x2){
        
    	if(lo+2 == hi){
        
    		x1 = (A[0] > A[1]) ? A[0] : A[1];
    		x2 = (A[0] < A[1]) ? A[0] : A[1};  
    		//T(2) = 1
    	}
    	if(lo+3 == hi){
        
    		x1 = (A[0] > A[1]) ? ((A[0] > A[3]) ? A[0] : A[3]) : ((A[1] > A[3]) ? A[1] : A[3]);
    		x1 = (A[0] < A[1]) ? ((A[0] < A[3]) ? A[0] : A[3]) : ((A[1] < A[3]) ? A[1] : A[3]);
    		//T(3) <= 3
    	}
    	int mi = (lo+hi)/2;  //divide
    	int x1L, x2L; 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;
    	}  //1 + 1 = 2
    }  //T(n) = 2*T(n/2) + 2 <= 5n/3 - 2 (初始条件：T(3)<=3)

[Link 1]: https://blog.csdn.net/qq_16497423/article/details/104832897