算法篇——算法分析
目录
一些数学定义
给定两个函数f和g，
1. 如果有正的常数c和n，使得当N≥n时，f(N) ≤ g(N)，那么f(N) = O(g(N))
2. 如果有正的常数c和n，使得当N≥n时，f(N) ≥ g(N)，那么f(N) = Ω(g(N))
3. 如果f(N) = O(g(N))，并且f(N) = Ω(g(N))，那么f(N) = Θ(g(N))
以上的定义在函数之间建立了一种级别，增长率高的，级别要高，比如。
对于和
，虽然当x较小时，f较大，但是g的增长率更大，当x≥1000时，f≤g，所以有f = O(g).
我们比较两个函数时，通常忽略系数和较低项，只保留最高项对比，比如和
，其实我们就是对比
和
，只比较最高项。根据下图，当N到达150时，除了N^3，其余函数已经混为一片，可以看出差一个数量级，随着N的增长，差别是巨大的。
常用函数增长率：
时间复杂度
一个算法耗费多少时间一般只有执行后才知道，但是我们可以在运行前大概估算算法的事件。
算法的时间复杂度是一个函数，它定性描述该算法的运行时间。我们通常计算需要的基本操作数量来表示时间复杂度。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
比如要计算一个n*n数组元素的和，我们要进行n^2次加法，那么这个算法的时间复杂度就为O(n^2)。随着n的增加，不同的复杂度差别是巨大的，如下图，因此在写一个算法之前应当先考虑好，尽量简化算法复杂度
最大子序列和问题
给定一个整数序列A1, A2, A3, ... An，求其子序列和的最大值。[1]
例如：A = -8，14，5，-3，6，8，-14，10，最大值为30，从A2到A6。
解法1:
穷举所有的子序列然后进行计算，如下：
int findmax1(vector<int> & L){
int max_value = 0;
for(int i=0;i<L.size();i++){
for(int j=i;j<L.size();j++){
int temp =0;
for(int k=i;k<=j;k++){
temp = temp + L[k];
}
if(temp>max_value)
max_value = temp;
}
}
return max_value;
}分析：
一共n个数，从第i个数开始的子序列有n-i个，一共要计算的加法次数是:
那么n个数一共要计算的加法次数是:
解法2:
对于从一个数开始的子序列，我们没有必要反复的从这个数开始计算，解法1中我们计算了：1，1+2，1+2+3，1+2+3+4....
我们可以表示为k = 1, k = k+2, k = k+3......这个算法的时间复杂度是O(n^2)
int findmax2(vector<int> & L){
int max_value = 0;
for(int i=0;i<L.size();i++){
int temp =0;
for(int j=i;j<L.size();j++){
temp = temp+L[j];
if(max_value<temp)
max_value = temp;
}
}
return max_value;
}解法3:
在队列中间劈一刀，最大子队列要么在左半部分，要么在右半部分，要么在中间，如下
对于一个序列我们将其分为两部分，分别计算左部分最大值，右部分最大值，然后从中间依次向左向右寻找最大值，找到中间部分最大值，比较三者大小，可以得出最大子队列。这里计算左部分最大值和右部分最大值要递归
int findmax3(vector<int> &L,int start,int end){
if(start == end){
if(L[start]>0)
return L[start];
else
return 0;
}
int m = (start+end)/2;
//计算左半部分最大子序列
int left_max = findmax3(L,start,m);
//计算右半部分最大子序列
int right_max = findmax3(L,m+1,end);
int m2left = 0;
int m2right = 0;
int temp = 0;
//从中间逐步向左计算最大值
for(int i=m;i>=start;i--){
temp += L[i];
if(temp>m2left)
m2left = temp;
}
//从中间逐步向右计算最大值
temp = 0;
for(int i=m+1;i<=end;i++){
temp += L[i];
if(temp>m2right)
m2right = temp;
}
//m2left+m2right就是中间部分的最大子序列h值
if(left_max>right_max)
return max(left_max,m2left+m2right);
else
return max(right_max,m2left+m2right);
}分析：
每次砍一半，所以一共砍logN次，为了计算中间的最大序列，我们要从middle开始分别向左向右扫描，这个复杂度是N。
第一层如下：
第二层划分为两段，每段扫描N/2个元素，还是N个
第三层划分为4段，每段扫描N/4个元素，还是N个
所以一共logN层，每层扫描N个元素，复杂度为O(NlogN)
解法4
最大子序列的开头肯定不是负数，同样的，对于第i个和第j个元素，如果从i到j的子序列和为负值，那么从i到j一定不是最优子序列的开头。该算法的复杂度显然为O(N)
int findmax4(vector<int> &L){
int max_value = 0,temp = 0;
for(int i=0;i<L.size();i++){
temp += L[i];
if(temp>max_value)
max_value = temp;
if(temp<0)
temp = 0;
}
return max_value;
}
[1] Mark Allen Weiss. 数据结构与算法分析。北京：电子工业出版社，2016:45-54