1.算法的概念
程序运行时需要的资源有两种
时间：程序运行需要的时间。
空间：程序运行需要的存储空间。
什么是算法
算法是求解问题的一系列计算步骤，用来将输入数据转换成输出结果 ：
输入---->算法---->输出
如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是正确的。
算法设计应满足以下几条目标：
1.正确性
2.可使用性
3.可读性
4.健壮性
5.高效率与低存储量需求
算法具有以下5个重要特征：
1.有限性
2.确定性
3.可行性
4.输入性
5.输出性
算法和数据结构
算法与数据结构既有联系又有区别。
联系：数据结构是算法设计的基础。算法的操作对象是数据结构，在设计算法时，通常要构建适合这种算法的数据结构。数据结构设计主要是选择数据的存储方式，如确定求解问题中的数据采用数组存储还是采用链表存储等。算法设计就是在选定的存储结构上设计一个满足要求的好算法。
区别：数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。
算法设计的基本步骤
1.分析求解问题
2.选择数据结构和算法设计策略
3.描述算法
4.证明算法的正确性
5.算法分析
2.算法分析
算法分析是分析算法占用计算机资源的情况。
所以算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。
算法时间复杂度分析
1.复杂度分析概述
一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，算法的运行时间取决于两者的综合效果。
bool Solve(double a[][MAX],int m,int n,double &s)
{
int i; s=0;//顺序结构
if (m!=n) return false;//分支结构
for (i=0;i<m;i++)//循环结构
s+=a[i][i];
return true;//顺序结构
}
设n为算法中的问题规模，通常用大O、大Ω等两种渐进符号表示算法的执行时间与n之间的一种增长关系。
定义1（大O符号），f(n)=O(g(n))（读作“f(n)是g(n)的大O”）当且仅当存在正常量c和n0，使当n≥n0时，f(n)≤cg(n)，即g(n)为f(n)的上界.
如3n+2=O(n)，因为当n≥2时，3n+2≤4n。
10n2+4n+2=O(n4)，因为当n≥2时，10n2+4n+2≤10n4。
大O符号用来描述增长率的上界，表示f(n)的增长最多像g(n) 增长的那样快，也就是说，当输入规模为n时，算法消耗时间的最大值。这个上界的阶越低，结果就越有价值，所以，对于10n2+4n+2，O(n2)比O(n4) 有价值。
一个算法的时间用大O符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑上界”或“紧确上界”。
定义2（大Ω符号），f(n)=Ω(g(n))（读作“f(n)是g(n)的大Ω”）当且仅当存在正常量c和n0，使当n≥n0时，f(n)≥cg(n)，即g(n)为f(n)的下界。
如3n+2=Ω(n)，因为当n≥1时，3n+2≥3n。
10n2+4n+2=Ω(n2)，因为当n≥1时，10n2+4n+2≥n2。
大Ω符号用来描述增长率的下界，表示f(n)的增长最少像g(n) 增长的那样快，也就是说，当输入规模为n时，算法消耗时间的最小值。
与大O符号对称，这个下界的阶越高，结果就越有价值，所以，对于10n2+4n+2，Ω(n2)比Ω(n) 有价值。一个算法的时间用大Ω符号表示时，总是采用最有价值的g(n)表示，称之为“紧凑下界”或“紧确下界”。
算法的最好情况是指算法在所有输入I下所执行基本语句的最少次数。
算法的最坏情况为是指算法在所有输入I下所执行基本语句的最大次数。
2.非递归算法时间复杂度分析
对于非递归算法，分析其时间复杂度相对比较简单，关键是求出代表算法执行时间的表达式。
通常是算法中基本语句的执行次数，是一个关于问题规模n的表达式，然后用渐进符号来表示这个表达式即得到算法的时间复杂度。
3.递归算法的时间复杂度分析
递归算法是采用一种分而治之的方法，把一个“大问题”分解为若干个相似的“小问题”来求解。
对递归算法时间复杂度的分析，关键是根据递归过程建立递推关系式，然后求解这个递推关系式，得到一个表示算法执行时间的表达式，最后用渐进符号来表示这个表达式即得到算法的时间复杂度。
算法空间复杂度分析
一个算法的存储量包括形参所占空间和临时变量所占空间。在对算法进行存储空间分析时，只考察临时变量所占空间。
3.算法设计工具——STL
STL概述
STL主要由container（容器）、algorithm（算法）和iterator（迭代器）三大部分构成，容器用于存放数据对象（元素），算法用于操作容器中的数据对象。
什么是STL容器
一个STL容器就是一种数据结构，如链表、栈和队列等，这些数据结构在STL中都已经实现好了，在算法设计中可以直接使用它们。
标签：符号,复杂度,4n,算法,时间,数据结构 From： https://www.cnblogs.com/114514tshe/p/16989631.html