算法-Mooc-浙江大学

1.算法的概念

  • 一个有限指令集
  • 接受一些输入(有时不需要输入)
  • 产生输出
  • 在有限步骤之后终止
  • 每一条指令必须:
    <1>.有充分目标,不可以有歧义
    <2>.计算机能处理的范围内
    <3>.描述不依赖任何一种计算机语言以及具体实现手段

2.评判好算法指标

  1. 空间复杂度S(n):程序执行时占用存储单元的长度
  2. 时间复杂度T(n):程序执行时耗费时间的长度

3.分析算法好坏所关注的复杂度

  1. 最坏情况复杂度(一般分析这个)
  2. 平均复杂度

4.复杂度排序

算法-Mooc-浙江大学tips:

  • logn不写底是因为无关紧要,都一样
  • 作为程序员,遇到n的二次方试着将其降为nlogn

5.复合算法复杂度

  1. 若两段算法的复杂度分别为:T1(n)=O(f1(n)),T2(n)=O(f2(n))则:

    <1>.T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))
    <2>.T1(n)*T2(n)=O(f1(n)*f2(n))

  2. for:循环次数*循环体代码的复杂度

  3. if-else:取决于if条件复杂度和两个分支部分复杂度,总体复杂度取三者中最大

6.应用实例-最大子链和

给定N个整数的序列,求最大子链和,若结果为负,返回0;

  1. 方法1:复杂度-N的三次方
    暴力的三次循环求解

  2. 方法2:复杂度-N的二次方
    改进ThisSum求和的一步,每次求和都是在原有的基础之上继续加了一个数,让原本第三个for下的运算跟着第二个走

  3. 方法3:复杂度-nlogn-分而治之
    <1>.[4,-3,5,-2,-1,2,6,-2]首先将其分为左[4,-3,5,-2],右[-1,2,6,-2]两个部分
    <2>.继续分:[4,-3],[5,-2],[-1,2],[6,-2]

    <3>.[4,-3],以4和-3的中间向左右两边扫描,左最大4,从中向左最大4,右边最大-3,从中向右最大-3,子链{4,-3}最大 = (从中向左最大+从中向右最大)=1,[4,-3]最大 = max(左最大,右最大,子链{4,-3}最大 )=4
    <4>.同理 [5,-2]最大 = 5

    <5>.[4,-3,5,-2],以[4,-3]和[5,-2]的中间向左右两边扫描,左最大4,从中向左最大1,右边最大5,从中向右最大3,子链{4,-3,5,-2}最大 = (从中向左最大+从中向右最大)=4,[4,-3]最大 = max(左最大,右最大,子链{4,-3,5,-2}最大 )=5
    <5>.同理[-1,2,6,-2]最大 = 8

    <6>.[4,-3,5,-2,-1,2,6,-2],以[4,-3,5,-2]和[-1,2,6,-2]的中间向左右两边扫描,左最大5,从中向左最大4,右边最大8,从中向右最大7,子链{4,-3,5,-2,-1,2,6,-2}最大 = (从中向左最大+从中向右最大)=11,[4,-3,5,-2,-1,2,6,-2]最大 = max(左最大,右最大,子链{4,-3,5,-2,-1,2,6,-2}最大 )=11

  4. 方法4:复杂度-N-在线处理
    [-3,1,-2,2,-1,2,-3]从左向右依次扫描,-3抛弃,max = 0,整个结果加上负数结果一定会比原来小;1,保留,max = 1;1-2=-1,负数抛掉,max = 1;2保留,max = 2;2-1 = 1保留,max = 2;1+2 = 3保留,max = 3;3-3 = 0保留,max = 3;故max = 3

#include<iostream>

using namespace std;

int N = 8;
int A[8] = {4,-3,5,-2,-1,2,6,-2};

int MaxSubseqSum1(int A[],int N); //way1 
int MaxSubseqSum2(int A[],int N); //way2
int MaxSubseqSum3(int A[],int left,int right); //way3
int MaxSubseqSum4(int A[],int N); //way4
int max3(int a,int b, int c); //获取a,b,c中最大值 

int main(){
	int result;
	//result = MaxSubseqSum1(A,N);
	//result = MaxSubseqSum2(A,N);
	result = MaxSubseqSum3(A,0,N-1);
	//result = MaxSubseqSum4(A,N);
	
	cout<<result<<endl;
	
	return 0;
}

int MaxSubseqSum1(int A[],int N){
	int MaxSum = 0;
	for(int i=0;i<N;i++){
		for(int j=i;j<N;j++){
			cout<<"MaxSum:"<<MaxSum<<endl;
			int ThisSum = 0;
			for(int k=i;k<j;k++){
				ThisSum += A[k];
			}
			if(ThisSum>MaxSum){
				MaxSum = ThisSum;
			}
		}
	}
	return MaxSum;
}

int MaxSubseqSum2(int A[],int N){
	int MaxSum = 0;
	for(int i=0;i<N;i++){
		int ThisSum = 0;
		for(int j=i;j<N;j++){
			ThisSum += A[j];
			cout<<"MaxSum:"<<MaxSum<<endl;
			if(ThisSum>MaxSum){
				MaxSum = ThisSum;
			}
		}
	}
	return MaxSum;
}

int MaxSubseqSum3(int A[],int left,int right){
	
	if(left == right){
	//分到底的情况 
		if(A[left] > 0){
			return A[left];
		}
		else{
			return 0;
		}
	}
	
	int center = (left+right)/2; //1/2为0,向0取整
	
	int maxLeft = MaxSubseqSum3(A,left,center); //递归获取左右两端的最大值 
	int maxRight = MaxSubseqSum3(A,center+1,right);	
	
	int leftBorderSum = 0;
	int leftBorderMax = 0;
	for(int i=center;i>=left;i--){
		//左边最大值 
		leftBorderSum += A[i];
		if(leftBorderSum > leftBorderMax){
			leftBorderMax = leftBorderSum;
		} 
	}
	
	int rightBorderSum = 0;
	int rightBorderMax = 0;
	for(int i=center+1;i<=right;i++){
		//右边最大值 
		rightBorderSum += A[i];
		if(rightBorderSum > rightBorderMax){
			rightBorderMax = rightBorderSum;
		} 
	}
	
	return max3(maxLeft, maxRight, leftBorderMax + rightBorderMax); 
}

int MaxSubseqSum4(int A[],int N){
	
	int MaxSum,ThisSum = 0;
	MaxSum = ThisSum = 0;
	
	for(int i=0;i<N;i++){
		ThisSum += A[i];
		if(ThisSum>MaxSum){
			MaxSum = ThisSum;
		}
		else if(ThisSum < 0){
			ThisSum = 0;
		}	
		cout<<"MaxSum:"<<MaxSum<<endl;
	}
	return MaxSum;
}

int max3(int a,int b, int c){
	int max = a>b?a:b;
	max = max>c?max:c;
	return max;
}
上一篇:中国大学MOOC-陈越、何钦铭-数据结构(第二次课2-1)


下一篇:吉林大学超星MOOC学习通高级语言程序设计 C++ 实验04 数组及其在程序设计中的应用(2021级)(2)