8.1 算法分析初步
尽管直观，适用范围广，但枚举，回溯等暴力方法常常无法走出低效的阴影
越是通用的算法，越不能深入挖掘问题的特殊性
本章介绍一些经典问题的高效算法，由于是量身定制，这些算法从概念思路到程序实现都是千差万别的
本章开始，读者刚刚开始接触严肃的算法设计理论
算法分析初步所需要解决的问题就是在写程序之前按估计程序的时空开销，并作出决策，如果算法又复杂速度又慢，就可以先缓缓，等下写
8.1.1 渐进时间复杂度
最大连续和问题
最简单的方法就是枚举，得出如下程序
点击查看代码
tot = 0;
best = A[1];//初始化最大值
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) { //检查连续子序列A[i],...,A[j]
int sum = 0;
for(int k = i; k <= j; k++) { sum += A[k]; tot++; }//累加元素和
if(sum > best) best = sum; //更新最大值
}
注意这边best的初值是A[1]，这是最保险的做法，不要写best=0，因为未必序列中存在非负数，可能全都是负数
这边计算的tot与机器的运行速度无关，不同机器的速度不一样，运行时间也会有差异，但tot值一定相同。换句话说，它去掉了机器相关的因素，只衡量算法的工作量大小，依旧是加法操作的次数
统计程序中“基本操作”的数量，可以排除机器速度的影响，衡量算法本身的优劣程度
在本题中，将加法操作作为基本操作，类似地可以把其他四则运算，比较运算作为基本操作，一般不会严格定义基本操作的类型，而是根据不同情况灵活处理
可以计算得出输入规模为n时，其加法操作次数为T(n) = n(n+1)(n+2)/6
上面的式子在n很大的情况下，平方项和一次项对式子的影响不大，也就是T(n) = O(n^3)
这二者是同阶的，具体可以参考高数的同阶无穷大的定义
同阶的含义简单来说就是增长情况相同，我们可以只保留最大项，并忽略其系数，得到的简单式子称为算法的渐进时间复杂度(asymptotic time complexity)
基本操作的数量往往可以写成关于输入规模的表达式，保留最大项并忽略系数后的简单表达式称为算法的渐进时间复杂度，用于衡量算法中基本操作数随规模的增长情况
点击查看代码
#include
#include
using namespace std;
int main() {
clock_t start, end;
start = clock();
int n, tot = 0;
cin >> n;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
tot++;
}
}
}
end = clock();
cout << (double)(end-start) / CLOCKS_PER_SEC << endl;
return 0;
}
以上的代码可以体会到n扩大2倍的时候，时间的扩大近似8倍，注意这边只是近似，因为对于进本操作来说我们这里忽略了其他运算，并且一次项二次项我们也忽略了
尽管如此，算法分析的效果还是比较精确的，因为抓住了主要矛盾————执行的最多的运算是加法
渐进时间复杂度忽略了很多因素，因而分析结果只能作为参考，并不是精确的。尽管如此，如果成功抓住了最主要的运算量所在，算法分析的结果常常十分有用
8.1.2 上界分析
每次都要作一番复杂的数学推到才能得到渐进时间复杂度吗？当然不必
下面是另外一种推导方法，算法包含三层循环，内层最坏情况下需要循环n次，中层循环最坏情况下也需要n次，外层循环最坏情况下仍然需要n次，因此总运算次数不超过n^3，这里采用了上界分析，假定所有最坏情况同时取到，尽管这是不可能的。不难预料，这样的分析和实际情况肯定会有一定的偏差，但是数量级是正确的，上界也有记号：T(n) = O(n^3)
在算法设计中，常常不进行精确分析，而是假定各种最坏情况同时取到，得到上界。在很多情况下，这个上界和实际情况同阶（称为“紧”的上界），但也有可能会因为分析方法不够好，得到“松”的上界
松的上界也是正确的上界，但可能让人过高估计程序运行的时间（从而不敢编写程序），而即使上界是紧的，过大(100)或者过小(1/100)的最高想系数同样可能引起错误的估计
换句话说，算法分析不是万能的，要谨慎对待分析结果，如果预感到上界不紧，系数过大或者过小，最好还是要编程实践一下
点击查看代码
S[0] = 0;
for(int i = 1; i <= n; i++) S[i] = S[i-1] + A[i]; //递推前缀和S
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++) best = max(best, S[j]-S[i-1]);//更新最大值
//S[j]-S[i-1]:从i到j的序列和
注意上面的程序用到了递推的思想，从小到大依次计算S[1],S[2],S[3],...,每个只需要在前一个的基础上加上一个元素，换句话说，“计算S”这个步骤的时间复杂度为O(n)
接下来一个二重循环，用类似的方法可以分析出：
T(n) = n(n+1)/2
用上街分析可以更快的得出结论，内存循环最坏情况下要执行n次，外层也是，所以时间复杂度为O(n^2)
8.1.3 分治法
现在使用分治法来解决这个问题
分治的思想如下：
划分问题：把问题的实例划分成子问题
递归求解：递归解决子问题
合并问题：合并子问题的解得到原问题的解
以本题为例：
划分：就是把序列元素个数尽量相等的两半
递归：就是分别求出完全位于左半边或者完全位于右半的最佳序列
合并：就是求出起点位于左半，终点位于右半的最大连续和序列，并和子问题比较
以下是笔者尝试的比较n^3和nlogn的时间耗费
点击查看笔者代码
#include
#include
#include
#include
using namespace std;
constexpr int MAXN = 5000, MAXM = 100;
int num[MAXN];
void setD(int& len) {
for(int i = 0; i < len; i++) num[i] = rand()%MAXM - MAXM/2;
}
int bs(int x, int y) {
if(x+1 == y) return num[x];
int center = (x+y)/2;
int m1 = bs(x, center), m2 = bs(center, y);
int b1 = num[center-1], b2 =num[center], sum = 0;
for(int i = center-1; i >= x; i--) {
sum += num[i];
if(sum > b1) b1 = sum;
}
sum = 0;
for(int i = center; i < y; i++) {
sum += num[i];
if(sum > b2) b2 = sum;
}
int m3 = b1 + b2;
if(m1 > m3 && m1 > m2) return m1;
else if(m2 > m3) return m2;
else return m3;
}
int main() {
srand(time(NULL));
int len = MAXN + rand()%MAXN;
setD(len);
clock_t start, end;
start = clock();
int best = num[0];
for(int i = 0; i < len; i++) {
for(int j = i; j < len; j++) {
int sum = 0;
for(int k = i; k <= j; k++) {
sum += num[k];
}
if(sum > best) best = sum;
}
}
end = clock();
cout << (double)(end-start)/CLOCKS_PER_SEC << endl;
cout << best << endl;
start =clock();
cout << bs(0, len) << endl;
end = clock();
cout << (double)(end-start)/CLOCKS_PER_SEC << endl;
return 0;
}