一、算法的概念
1.算法的定义
书上定义：算法是指解决方案的准确且完整的描述，是一系列解决问题的清晰指令。
简易说法：算法是解决问题的方法与步骤
2.算法的五个重要特性
有限性：每个算法都要执行有限步之后结束
确定性：每一个步骤要有确切的含义，不能出现二义性
可行性：每一条运算能精确的执行（例如：不能出现除数为0）
输入性：一个算法有零个或多个输入
输出性：一个算法有一个或多个输出
二、算法分析
1.时间复杂度：分析算法的执行效率
常见的时间复杂度：O（1）， O（logn），O（n），O（nlogn），O（n2），O（2的n次方），O（n!）
O（1）：执行时间是固定的
int fun(int n)
{
int i=n; //假设一条语句的执行时间为a（a为常数）
int j=3*n;
return i+j;
} //这段代码的执行时间为2a，执行时间是固定的O（logn）：出现在乘法
int fun(int n)
{
int i=1; //执行时间设为a
while(i<=n) //执行时间为a（logn +1）【+1是因为最后一次做了判断知识不符合条件所以没有执行循环体】
i=i*2; //设执行次数为x，2的x次方=n，x=log2n，一般省略2，直接写为logn，执行时间为a(logn)
return i;
} //总共执行时间为：a+a(logn +1)+a(logn)=2a(logn)+2a,省去常数，因此时间复杂度为：O(logn)O（n）:出现累加
int fun(int n)
{
sum=0; //设执行时间为常数a
for(int i=0;i<n;i++) //执行次数为n+1，执行时间为a(n+1)
sum=+i; //执行次数为n次，执行时间为an
return sum;
} //总共执行时间为2an+2a,常数忽略不计，所以时间复杂度为O（n）O（m+n）：
int fun(int m,int n)
{
int sum=0; //设执行时间为常数a
for(int i=1;i<=m;i++) //执行次数为m+1，执行时间为a（m+1）
sum+=i; //执行次数为m，执行时间为am
for(int i=2;i<=n;i++) //执行次数为n，执行时间为an
sum+=i; //执行次数为n-1，执行时间为a（n-1）
return sum;
} //总共执行时间为：2am+2an+a，常数忽略不计所以是O（m+n）
通过这几次代码可以看出，只要找到起决定作用的代码，就可以直接指导时间复杂度，所以，后面算时间复杂度可以直接找主体代码。
如果出现嵌套循环，则是里面一个循环的时间复杂度乘以外面一个循环的时间复杂度。
时间复杂度排序：O（1）< O（logn）< O（n）< O（nlogn）< O（n2）< O（2的n次方）< O（n!）
2.空间复杂度：算法所占内存
O（1）：
int fun(int n)
{
sum=0;
for(int i=0;i<n;i++)
sum+=i;
return sum;
} //开辟了两个空间为sum、i，这两个空间为固定的因此为O（1）O（n）：
int fun(int n)
{
int arr[N];
while (i<=N)
i=i*2;
return i;
} //这段代码开辟的空间由N决定，因此空间复杂度为O（n）常见的空间复杂度排序：O（1）< O（n）< O（n2）
三、练习题
1.写出下面代码的空间复杂度：
int fun(int m,int n)
{
int arr[M][N];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
sum+=arr[i][j];
return sum;
}2.写出下面代码的时间复杂度：
int fun(int m,int n)
{
sum=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;)
{
sum+=i*j;
j=j+2;
}
}
return sum;
}
int fun(int n)
{
sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
sum+=i*j;
}
}
return sum;
}