算法设计与优化——前n项和计算

大家好，欢迎来到IT知识分享网。

文章目录

• @[toc]
• 1. 线性O(n)
• • 时间复杂度
• 2. 线性递归O(n)
• • 时间复杂度
  • 空间复杂度
• 3. 二分递归版O(n)
• • 时间复杂度
  • 空间复杂度

1. 线性O(n)

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) } //O(1) + O(n)*O(1) + O(1) = O(n+2) = O(n) 

时间复杂度

首先，对s的初始化需要O(1)时间。算法的主体部分是一个循环，每一轮循环中只需进行一
次累加运算，这属于基本操作，可在O(1)时间内完成。每经过一轮循环，都将一个元素累加至s，故总共需要做n轮循环。
O(1) + O(1) x n = O(n + 1) = O(n)

2. 线性递归O(n)

若n = 0则总和必为0，这也是最终的平凡情况；否则一般地，总和可理解为前n – 1个整数（A[0, n – 1)）之和，再加上末元素（A[n – 1]）。按这一思路，可基于线性递归模式设计。

int sum ( int A[], int n ) { 
    //数组求和算法（线性递归版） if ( 1 > n ) //平凡情况，递归基 return 0; //直接（非递归式）计算 else //一般情况 return sum ( A, n - 1 ) + A[n - 1]; //递归：前n - 1项之和，再累计第n - 1项 } //O(1)*递归深度 = O(1)*(n + 1) = O(n) 

时间复杂度

为解决问题sum(A, n)，需递归地解决问题sum(A, n – 1)，然后累加上A[n – 1]。按照这一新的理解，求解sum(A, n)所需的时间，应该等于求解sum(A, n – 1)所需的时间，另加一次整数加法运算所需的时间。
           ~~~~~~~~~~            根据以上分析，可以得到关于T(n)的如下一般性的递推关系：
                ~~~~~~~~~~~~~~~                T(n) = T(n – 1) + O(1) = T(n – 1) + c1， 其中c1为常数
           ~~~~~~~~~~           另一方面，当递归过程抵达递归基时，求解平凡问题sum(A, 0)只需（用于直接返回0的）常数时间。如此，即可获得如下边界条件：
                ~~~~~~~~~~~~~~~                T(0) = O(1) = c2， 其中c2为常数
联立以上两个方程，最终可以解得：
                ~~~~~~~~~~~~~~~                T(n) = c1n + c2 = O(n)

我试着从微分方程角度解释求解过程

T(n) = T(n – 1) + O(1) = T(n – 1) + c1， 其中c1为常数
T(0) = O(1) = c2， 其中c2为常数
微分方程角度看
$\frac{\Delta y}{\Delta x}$ = $\frac{T(n)-T(n-1)}{n-(n-1)}$ = c1
即 $y^{\prime }$ = c1
y = c1x + c
因为 T(0) = O(1) = c2
所以 c = c2
即 y = c1x + c2
综上
T(n) = c1n + c2 = O(n)

空间复杂度

设采用该算法对长度为n的数组统计总和，所需空间量为S(n)
S(1) = O(1)
S(n) = S(n – 1) + O(1)
两式联合求解即得：
S(n) = O(n)

3. 二分递归版O(n)

以居中的元素为界将数组一分为二；递归地对子数组分别求和；最后，子数组之和相加即为原数组的总和。

int sum ( int A[], int lo, int hi ) { 
    //数组求和算法（二分递归版，入口为sum(A, 0, n)） if ( hi - lo < 2 ) return A[lo]; //递归基：区间宽度不足2 int mi = ( lo + hi ) >> 1; //（否则）均分原区间 return sum ( A, lo, mi ) + sum ( A, mi, hi ); //递归求和，然后合计 } //O(hi - lo)，线性正比于区间的长度 

时间复杂度

与线性递归版sum()算法一样，此处每一递归实例中的非递归计算都只需要常数时间。递归实例共计2n – 1个，故新算法的运行时间为O(2n – 1) = O(n)，与线性递归版相同。

空间复杂度

算法启动后经连续m = $lo{g}_{2}n$次递归调用，数组区间的长度从最初的n首次缩减至1，并到达
第一个递归基。实际上，刚到达任一递归基时，已执行的递归调用总是比递归返回多m = $lo{g}_{2}n$次。更一般地，到达区间长度为$2^k$的任一递归实例之前，已执行的递归调用总是比递归返回多m-k次。因此，递归深度（即任一时刻的活跃递归实例的总数）不会超过m + 1。鉴于每个递归实例仅需常数空间，故除数组本身所占的空间，该算法只需要O(m + 1) = O(logn)的附加空间。

线性递归版sum()算法共需O(n)的附加空间，就这一点而言，新的二分递归版sum()算法有很大改进。