文章目录

前言

接下来更新的是数据结构的内容，用书：《Data Structures and Algorithm Analysis in C》，本章为书中第二章——算法分析。

数学基础

定义

在算法分析中，比较两个函数的增长我们一般使用相对增长率(relative rate of growth)作为量度。例如函数F(N)=1000N与函数H(N)=N^2，我们直接比较是没用的，因为它们会相交。

在N比较小的时候，F(N)>H(N)；当N=1000的时候，F(N)=H(N)，此时我们找到了一个转折点。接下来我们来看一个定义：

定义1：如果存在正常数c和n0使得当N >=n0时，T(N)<=cf(N)，则记为T(N)=O(f(N))；用T(N)表示上界的集合。

此时回到F(N)和H(N)，当N=1000时，F(N)=cH(N)，此时c=1。因为F(N)和H(N)都是增函数，根据上面的定义当N>=1000时，F(N)<=H(N)，那么我们就可以写成：F(N)=O(H(N))，即1000N=O(N^2)，这种记法称为大O记法。

换成我们熟悉的不等式讲法，就是：F(N) 的增长率小于等于H(N)的增长率。

我们还有一个类似的定义：

定义2：如果存在正常数c和n0使得当N >=n0时，T(N)>=cg(N)，则记为T(N)=Ω(g(N))；用T(N)表示下界的集合。

相反的，我们可以知道第二个定义是：T(N) 的增长率大于等于g(N)的增长率。

只有大于小于不行，于是还有两个定义：

定义3：T(N)=θ(h(N))，当且仅当T(N)=O(h(N))且T(N)=Ω(h(N))；
定义4：如果T(N) = O(p(N))，且T(N) ！= θ(p(N))，则T(N) = o(p(N))。

很容易知道，定义3描述的是T(N) 的增长率等于h(N)的增长率。例如，N^2与2N^2，它们只有系数的区别，但增长率是相同的。

而定义4说的是T(N)的增长率小于p(N)的增长率，它和大O记法不同的是它不能相等，即大O记法是小于等于，而小o记法是小于而已。

了解了这些定义以后还需要知晓一些法则。当我们说T(N) = O(f(N))时，我们是在保证函数T(N)是在以不快于f(N) 的速度增长；因此我们可以说f(N)是T(N)的一个上界（upper bound）；相同的若有T(N)=Ω(g(N))，那么说明g(N)是T(N)的一个下界(lower bound)。

结论

下面这些结论需要掌握：

如果T1(N)=O(f(N)) 且 T2(N)=O(g(N))，则
- T1(N) + T2(N) = max(O(f(N)) , O(g(N))),
- T1(N) * T2(N) = O(f(N) * g(N)).
如果T(N)是一个k次多项式，则T(N)=θ(N^k).
对任意常数k, (logN)^k = O(N) 。即对数增长得非常缓慢。

此外还有几点需要注意：

在大O里不要放入常数或低阶项，即不要出现T(N)=O(2N), 或T(N)=O(N^2+N)这种类似形式。即只需要简化为最高次项，低阶项一般可以被忽略，而常数也可以弃掉。此时，要求的精度是很低的。
我们可以通过数学方法计算极限 lim(N→∞)⁡ (f(N))/(g(N))来确定f(N) 和g(N) 的相对增长率。
- 当极限是0 ：这意味着f(N) = o(g(N)) 。
- 极限是一个常数c != 0 ：这意味着f(N)= θ(g(N))。
- 极限是∞：这意味着g(N) = o(f(N))。
- 极限摆动：二者无关。
不存在f(N) <= O(g(N))的情况，因为O函数已经包含了不等式。

运行时间计算

一般法则

在编写程序的时候，我们总希望尽早除去那些不好的算法思想，因此，通常需要对算法进行分析。不仅如此，进行分析的能力还有助于洞察到如何设计有效的算法。一般说来，分析还能准确确定需要仔细编码的瓶颈。

我们一般会有如下原则：

舍弃特定的时间单位和低次项，计算程序的上界作为运行时间。即计算大O运行时间

分析的结果为程序在一定的时间范围内能够终止运行提供了保障。程序可能提前结束，但绝不可能拖后。所以我们计算的运行时间为最大运行时间。

然而计算程序的时间我们一行行就算显然不太现实，于是经过长期的数学运算，我们可以通过以下法则来计算运行时间。

法则1——For循环：一次for循环的运行时间至多是该for循环内语句（包括测试）的运行时间乘以迭代的次数。

例如：

//Count sum of i^3
int sum(int N)
{
    int ans=0;
    for(int i=1;i<=N;i++)  //line 1
    {
        ans+=i*i*i; //line 2
    }
    return ans;
}

在line2中，每执行一次的运行时间是4个时间单元（第一个乘，第二个乘，相加，赋值），此时函数可以是F(t)=4；所以此时这一行的运行时间是O(1)。

然后在line1中，循环体需要执行N次，忽略首元素赋值和自增带来的开销，此时循环结束的运行时间就是O(N)。

所以根据法则1，这个函数的运行时间是循环体内运行时间X迭代次数，此时即O(1) X O(N) = O(N)。

故我们知道了这个函数的运行时间，即O(N)。

我们发现，大O计算会忽略系数，所以如果循环体内语句均为常数，那么整个循环体的运行时间就是O(N)。但如果不是全为常数呢，接下来看法则二。

法则2——嵌套的for循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for 循环的大小的乘积。

简单来说也是法则一的拓展，来看一个嵌套循环的例子：

for(int i=1;i<=N;i++)  //line1
    for(int j=1;j<=N;j++)  //line2
        ans+=i+j;  //line3

这是一个很简单的嵌套循环，我们从里向外分析。首先是line3，此时它很明显是一个O(1)的时间，然后到line2，运用法则1，我们知道它的时间是O(1) X O(N) = O(N)。而到了line1，这个循环（i的循环）的循环体是j的循环，j的循环的时间刚才我们知道是O(N)，则运用法则1，line1的时间是：O(N) X O(N) = O(N^2)，所以这个嵌套循环的时间就是O(N^2)。

于是就可以得到这样的规律：n重循环的最大运行时间是O(N^n)，当且仅当每个循环的迭代次数都是N。

如果循环迭代次数不一样的情况呢，这个之后会有例子解释。

接下来到我们最熟悉的情况，顺序结构。

法则3——顺序语句：将各个语句的运行时间求和即可（这意味着，其中的最大值就是所得的运行时间）

这个很显然，而根据大O计算法则，仅计算次项最高的函数体，所以其中的最大值就是所得的运行时间。

法则4——IF/ELSE语句：一个if/else 语句的运行时间从不超过判断再加上IF/ELSE语句中两者运行时间长者的总的运行时间。

简单来说，就是if/else语句中选择两者中运行时间最长的即可，这样的计算在某些情形下估计有些过高，但绝不会估计过低。

看完这些法则我们可以知道一个原则：分析的基本策略是从内部（或最深层部分）向外展开的。
如果有函数调用，那么这些调用要首先分析。如果有递归过程，那么存在几种选择。若递归实际上只是被薄面纱遮住的for循环，则分析通常是很简单的。

例如这种：

int fac(int N)
{
    if(N<=1) return 1;
    else
      return N*fac(N-1);
}

这是一个很明显的递归，实际上就是计算阶乘，完全可以用循环来代替。很显然，它的时间也是O(N).

但当递归被正常使用时，将其转换成一个简单的循环结构是相当困难的。在这种情况下，分析将涉及求解一个递推关系。例如计算斐波那契数列：

int fib(int N)
{
    if(N<=1) return 1;  //1
    else return fib(N-1)+fib(N-2);  //2
}

我们设T(N)函数为fib(N)的运行时间，当N<=1时，此时返回1，则T(N)=1，当且仅当N<=1。当N>=2时，此时T(N)的计算中计算1和2行中最大的运行时间，第二行的运行时间是一个常数计算（加法，赋值返回）和两个函数调用。因为我们设设T(N)函数为fib(N)的运行时间，所以此时第二行的运行时间为：T(N)=T(N-1)+T(N-2)+2；

根据斐波那契数列的公式我们知道，fib(N)=fib(N-1)+fib(N-2)，所以此时出现了：T(N)>=fib(N)。造成这种问题主要是，我们在计算fib(N-1)的时候，已经计算了fib(N-2)，而在之后又重复的计算，当N逐渐变大时，里面的运行时间均以乘法计算，最后就是指数增长了。这样的递归重复计算了多次，这样的算法就是应该舍弃的算法。

接下来我们通过一个完整的例子来看上面法则的混合运用。

最大子序列和问题的解

首先这个问题是指，在一个数组中寻找连续子序列之和的最大值。例如数组{1,-2,2,3,4}，它最大的子序列和是2+3+4=9，子序列需要是连续的。

我们最先可以想到的方法就是枚举每个子序列的和，取其最大值，例如：

int MaxSubsequenceSum( const int A[ ], int N )
{
            int ThisSum, MaxSum, i, j, k;

/* 1*/      MaxSum = 0;
/* 2*/      for( i = 0; i < N; i++ )
/* 3*/          for( j = i; j < N; j++ )
                {
/* 4*/              ThisSum = 0;
/* 5*/              for( k = i; k <= j; k++ ) 
/* 6*/                  ThisSum += A[k]; 
/* 7*/              if( ThisSum > MaxSum )
/* 8*/                  MaxSum = ThisSum;
                }
/* 9*/      return MaxSum;
}

很显然，这是一个O(N^3)的算法。虽然内层循环并不是N的迭代次数，所以实际上是θ(N^3)的算法，再准确一点是，我们将用到前N 个整数求和以及前N 个平方数求和的公式。

那这种算法是非常的缓慢的，我们肯定不希望在程序里运行这样时间长的代码，所以我们有如下改进。

减少一个for循环变成O(N^2)：

int MaxSubsequenceSum( const int A[ ], int N )
        {
            int ThisSum, MaxSum, i, j;

/* 1*/      MaxSum = 0;
/* 2*/      for( i = 0; i < N; i++ )
            {
/* 3*/          ThisSum = 0;
/* 4*/          for( j = i; j < N; j++ ) { 
/* 5*/                  ThisSum += A[ j ]; 
/* 6*/          if( ThisSum > MaxSum )
/* 7*/                  MaxSum = ThisSum;
                }
            }
/* 8*/      return MaxSum;
        }
/* END */

我们还可以采用一种分治的算法，把这个数组分成左右两部分。于是最大的子序列就会有三种情况：在左序列中，在右序列中，在两个序列之间。

左右两边序列的计算方法都是差不多的，我们可以使用递归解决，而中间的即把两边此时的临时和加起来，进行比较看看谁最大就返回谁。

int minsum(int a[], int left, int right) {
	int s,s0, s1, lf, rt;
	if (left == right)
		return a[left];
	else {
		int mid = (left + right)/2;
		int leftsum = minsum(a, left, mid);  //左子序列最大和
		int rightsum = minsum(a, mid + 1, right);  //右子序列最大和
		s0 = 0;  //左边临时和
		lf = 0;
		for(int i = mid; i >= 0; i--) {
			lf += a[i];
			if (lf > s0) {  //加上当前的数如果大于左边临时和，则更新左边临时和
				s0 = lf;
			}
		}
		s1 = 0;  //右边临时和
		rt = 0;
		for(i = mid + 1;i <= right; i++){ rt += a[i]; if (rt > s1) {
				s1 = rt;
			}
		}
		s = s0 + s1;
		if (s< leftsum&&rightsum < leftsum)
			return leftsum;
		else if (s<rightsum&&rightsum>leftsum)
			return rightsum;
		else
		{
			return s;
		}
 
	}
}

这个算法相当于是从中间开始计算，例如{4,-3,5,-2,-1,2,6,-2}

我们先分成{4,-3,5,-2} 和 {-1,2,6,-2}

此时mid=7/2=3，其实就是元素-2.于是开始计算，左侧的，右侧的，递归即可。

我们来计算一下运行时间：设运行时间为T(N)

我们看到有一个for循环，首先是一个O(N)，接下来两个函数递归调用，即2T(N/2)，故T(N) = 2T(N/2) + O(N)。当然，如果是1的话，即T(1)=1。然后来看看它有什么规律：

当N=2时，T(2)=2*1+2=4=2*2，T(4)=2*4+4=12=4*3，T(8)=2*12+8=32=8*4，T(16)=2*32+16=80=16*5。故我们发现T(N)=N*(k+1)，设N=2^k，k=logN，故T(N)=N*logN，所以带回去T(N)=N*logN + N = O(N*logN)。

根据数学知识，我们知道log的增长是非常的缓慢的，故这个算法的效率是挺高的。

那我们还有什么别的算法能更快嘛？我们知道线性的函数一般来说是效率最高的，NlogN>N，我们能不能把算法优化到O(N)呢。但我们发现这样的想法已经到了无法优化的时候了，于是可以想想除了递归分治之外的想法。

我们可以使用动态规划，算法的时间复杂度为 O(n)，能够在线性时间解决问题。该算法的一个附带的优点是，它只对数据进行一次扫描，一旦a[i]被读入并被处理，它就不再需要被记忆。

我们需要先知道下面的理解：

如果一个数是负数，那么它不可能是起点，任何负数序列不可能为最大子序列和的序列。
我们从第一个元素往后遍历，所记录元素的数组为a[]，对于这些输入的数组元素，我们设一个和thisSum，初始化为0。对应这个thisSum,我们设置一个记录最大数值和的元素maxSum，每次输入一个数组元素，如果thisSum比maxSum大，则进行更新。
如果thisSum<0，那么前面这一段的最大值已经记录完毕，存在maxSum里面，造成thisSum<0的原因是此时该元素<0，因此，在后面的元素的遍历中，不能继续使用该元素，因此，将thisSum置为0，继续从该元素的下一个元素为起点进行遍历。

int MaxSubsequenceSum( const int A[], int N )
        {
            int ThisSum, MaxSum, j;
/* 1*/      ThisSum = MaxSum = 0;
/* 2*/      for( j = 0; j < N; j++ ) { 
/* 3*/              ThisSum += A[ j ]; 
/* 4*/      if( ThisSum > MaxSum )
/* 5*/              MaxSum = ThisSum;
/* 6*/          else if( ThisSum < 0 )
/* 7*/              ThisSum = 0;
            }
/* 8*/      return MaxSum;
        }

其他法则

我们在之前的分治算法中发现计算对数的情况，总结出这个法则：

法则5——对数法则：如果一个算法用常数时间(O(1))将问题的大小削减为其一部分（通常是1/2) ，那么该算法就是O(NlogN)

同时还有：

法则6——线性法则：如果使用常数时间只是把问题减少一个常数（如将问题减少1) ，那么这种算法就是O(N) 的。

根据法则5的情况，我们很容易想到二分算法就是O(NlogN)的。当然还有我们经常使用的求最大公约数的辗转相除法（欧几里得算法）

int Gcd(unsigned int M,unsigned int N)
{
    unsigned int Rem;
    while(N > 0)
    {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}

根据规律：在两次迭代以后，余数最多是原始值的一半。故2 logN = O(log N)。

而幂运算也是这样的，快速幂的算法：

long long binaryPow(long long a, long long b, long long m){
	if(b == 0)
		return 1;
	else if(b % 2 == 1)   //或（b&1）执行速度更快 判断是否为奇数
		return a * binaryPow(a, b - 1, m) % m;
	else{
		long long num = binaryPow(a, b/2, m) % m;	//优化 
		return num * num % m;  // 不直接写成return binaryPow(a, b/2, m) * binaryPow(a, b/2, m)
	}
	
}

此时是O(logN)的运算时间。分析一下：