什么是算法
数据结构02
0x00 什么是算法
算法
1指令集有限
2产生输出
3有限步骤终止
4每条指令都必须明确目标，不能有歧义，不依赖语言
0x01 什么是好的算法
空间复杂度S(n) 算法在运行时占用储存单元的长度
时间复杂度T(n) 算法耗费时间的长度
一般关注算法在最坏情况的复杂度，因为平均复杂度不好衡量
复杂度的渐进表示法 表示算法在输入增长时的规模变化情况
T(n) = O(f(n)) 表示存在常数C>0,n0>0使得当n>n0时有T(n)<=C*f(n)
也就是O(f(n))时T(n)的上界
0X02 最大子列和问题
解法一：
不断调整左右边界，把每一种字串的和都计算出来，该种方式的时间复杂度为O(n^3)。
int maximum1(int * p,int size){
int i,j,k;
int max=-1000;
for(i=0;i<size;i++){
for(j=i;j<size;j++){
int sum=0;
for(k=i;k<=j;k++){
sum+=p[k];
}
if(sum>max){
max=sum;
}
}
}
return max;
}
解法二：
同样也是调整左右边界，但是该方法不是调整完边界后得到字串后，重新计算字串的和。而解法二则是先规定左边界，右边界从左边界开始，每次往右调整一次，就再上一次字串和的基础上加上新的数字，新的字串和比max大就成为max。该方法就两个循环。时间复杂度是O(n^2)
int maximum2(int * p,int size){
int i,j;
int max=-1000;
for(i=0;i<size;i++){
int sum=0;
for(j=i;j<size;j++){
sum+=p[j];
if(sum>max){
max=sum;
}
}
}
return max;
}
解法三：
这种解法是利用“分而治之”的思想，将长串分为两个字串，从左子串 右子串 以及跨越左右字串中找到 最大的字串和。1对于左字串 右子串，递归的求解，2对于跨左右字串，从中间起，分别往左往右增长字串长度，找到左右的最大字串和，然后加一起既是跨左右字串最大和。3然后返回三者中的最大值。
该种算法的时间复杂度为O(nlogn) ,因为由于递归二分，所以一共为logn次，而每次只有一个循环，故为nlogn。
int maximum3(int*p,int size){
if(size==1){
return p[0];
}
int halfsize=size/2;
int i=0;
int max=0;
int leftdata[halfsize];
int rightdata[halfsize];
int max_l,max_r,max_m;
for(i=0;i<halfsize;i++){
leftdata[i]=p[i];
rightdata[i]=p[i+halfsize];
}
max_l=maximum3(leftdata,halfsize);
max_r=maximum3(rightdata,halfsize);
int max_ml=0,max_mr=0;
int sum=0;
for(i=halfsize-1;i>=0;i--){
sum+=p[i];
if(sum>max_ml){
max_ml=sum;
}
}
sum=0;
for(i=halfsize;i<size;i++){
sum+=p[i];
if(sum>max_mr){
max_mr=sum;
}
}
max_m=max_ml+max_mr;
max=max_l;
if(max_l>max_r&&max_l>max_m) max=max_l;
if(max_m>max_l&&max_m>max_r) max=max_m;
if(max_r>max_l&&max_r>max_m) max=max_r;
return max;
}
解法四：
这种解法被称为在线求解，其思想是，对于已经算出的部分，如果知道其不可能是最大字串的一部分，就舍弃掉。
从左往右，一直求和，如果和小于0，则说明已经求和的部分，会让新加的字串和变小，不可能是最大字串和的一部分，应该舍去，重新开始计算和。该方法只遍历一次，故为O(n)。
int maximum4(int*p,int size){
int max=0;
int sum=0;
int i=0;
for(i=0;i<size;i++){
sum+=p[i];
if(sum<0) sum=0;
if(sum>max) max=sum;
}
return max;
}
