一、算法 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。
简单地说，算法是解决问题的方法和步骤。
二、算法的描述方式
描述算法的常用方式有：自然语言、流程图、伪代码、计算机编程语言等。
三、算法的特性
（1）有穷性：一个算法必须总在执行有穷步后结束，且每一步都可在有穷时间内完成。
（2）确定性：算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。
（3）可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。算法中每一步运算应该是可行的。算法原则上能够精确地运行，而且人能用笔和纸做有限次运算后即可完成。
（4）输入：一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。
（5）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计的目的。它们是同输入有着某种特定关系的量。
四、“好的算法”的标准
（1）正确性：算法能够正确地解决求解问题。
（2）可读性：算法应具有良好的可读性，以帮助人们理解。
（3）健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其名的输出结果。
（4）高效率与低存储需求：时间复杂度低，空间复杂度低。
五、算法的效率 算法效率分为时间效率与空间效率：
时间效率被称为时间复杂度——算法在执行时需要消耗的时间，衡量一个算法的运行速度。
空间效率被称为空间复杂度——算法在执行时需要消耗的内存大小，衡量一个算法所需的内存空间。
六、算法的时间复杂度
1. 什么是时间复杂度？ 算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比，算法中的基本操作的执行次数，为算法的时间复杂度。
算法运行需要的时间， 一般将语句执行次数作为时间复杂度：
int sum = 0; //运行1次
int total = 0; //运行1次
for (int i = 0; i < n; i++) //运行n次，所以 T(n) = 1 + 1 + n
total = total + i 时间复杂度用大写字母”O”表示，只保留数量级最大的一项，并忽略系数，所以上面的时间复杂度：O(n)。
问题：可以使用“先运行程序，事后统计运行时间”的方法来估算时间开销吗？
答：使用如此方法是不客观的，主要有以下几个原因：
◆ 机器性能越强，开销越少； 如：超级计算机 vs 单片机。
◆ 编程语言越高级，执行效率越低；如：Java写的程序要比用C写的效率低一些。
◆ 和编译程序产生的机器指令质量有关。
2. 大O的渐进表示法
实际中我们计算时间复杂度只需要计算大概执行次数，那么我们使用大O的渐进表示法。
大O符号：用于描述函数渐进式行为的数学符号
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
一个算法的计算的次数是 3N3+ N3 + 103 ，那么他的时间复杂度是O(N3)，取最高阶且忽略常数。通常情况下，算法的时间复杂度会使用某些固定操作被执行的次数，和n的关系来进行度量。
3. 时间复杂度有哪3种情况？
⚪ 最坏情况：任意输入规模的最大运行次数（上界）。
⚪ 平均情况：任意输入规模的期望运行次数。
⚪ 最好情况：任意输入规模的最小运行次数（下界） 。
时间负责度取最坏情况，即上面问题的时间复杂度表示为O(n)。
4. 常见的时间复杂度 哪种时间更长，哪种更节省时间呢？按照所消耗时间由少到多进行排序如下：
❶、常数阶 O(1) 比如下面这个算法，是利用高斯定理计算1, 2,…, n个数的和：sum = (1 + n) * n / 2。
❷、对数阶 O(logn) 也叫对数时间，比如二分算法。
❸、线性阶 O(n) 一层循环 for(i = 0; i < n; i++){}，它的循环的时间复杂度为O(n)， 因为循环体中的代码要执行n次。
❹、在线性阶和平方阶中间，有一个常见的复杂度O(n*logn)，比如快速排序、归并排序。
❺、平方阶 O(N2) 比如选择排序、冒泡排序。
❻、立方阶 O(N3) 比如三层循环，每层循环执行n次。
❼、O(2n) 比如求子集，子集枚举等 。
❽、O(n!) 旅行商问题：从一个城市出发，经过所有城市后返回出发地，求最短的路径。如果用朴素算法，第一个城市有n种选择，第二个有n-1种选择，依次类推，复杂度为O(n!)。
题目数据规模和时间复杂度 信息学竞赛中, 一般可以认为1s最多能执行108次运算：
5. 计算复杂度的两条规则
❶ 加法规则：多项相加，只保留最高阶的项，且系数变为1。 T(n,m) = T1(n) + T2(n) = O [ max ( f(n), g(m) ) ]
❷ 乘法规则：多项相乘，都保留。 T(n,m) = T1(n) * T2(m) = O [ f(n) * g(m) ]
七、空间复杂度：算法占用内存空间的大小
在计算机发展早期，计算机存储容量很小，很在意空间复杂度；但是时光流逝，如今计算机的存储容量已经非常大，所以空间复杂度被关注得不多了。
在信息学竞赛中，对解题的内存进行了限制，一般情况下，只要不是创建多个大容量的数组，存储空间都是够用。在解决问题时常常会采用空间换时间的策略，例如桶排序。
数据规模 信息学竞赛中一般是128M/256M/512M的空间限制。
256M = 256 * 1024 * 1024 = 268435456字节
128M = 131072KB = 134217728字节
128M的情况下，开int型变量的一维数组最多是3千万, long long型1千5百万, char型1亿左右
换成数组的最大值:
int a[3e7];
int a[5000][5000];
long long a[1e7];
long long a[4000][4000];
八、时间复杂度的计算具体步骤
1、 找出算法中的基本语句：算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
2、 计算基本语句的执行次数的数量级：
(1) 只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幕和最高次幕的系数。
(2) 这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
3、 用大O记号表示算法的时间性能：
(1) 将基本语句执行次数的数量级放入大O记号中。
(2) 如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。
九、常见算法的时间复杂度：
十：具体的时间测量方法
#include <ctime>
#include <iostream>
using namespace std;
const int MAXN = 1e7;
int main(){
int sum=0;
clock_t startTime=clock(); //开始时间
for(int i=1; i<=MAXN; i++) {
sum+=i;
}
clock_t endTime=clock(); //结束时间
cout<<double(endTime-startTime)/CLOCKS_PER_SEC<<"s"<<endl;
return 0;
}