1.什么是算法
算法(algorithm)是对某一特定类型的问题求解步骤的一种描述，是指定的有限序列，字面意思就是用于计算的方法。
算法特性
1.有穷性：一个算法总是会再执行有限次数后停止。
2.确定性：每个步骤都有确定的含义，对相同的输入有相同的输出。
3.输入：一个算法有零个或多个输入。
4.输出：一个算法有一个或多个输出。
5.可行性：算法中每一步都可以通过已经实现的基本运算的有限次运行来实现。
通常用算法的复杂度来衡量一个算法的好坏。那么，什么是复杂度呢？
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
3.1时间复杂度定义
算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。(注：一个算法的执行时间从理论上来说是不能算出来的，但算法花费的时间与其中语句的执行次数成正比例，因此算法中的基本操作的执行次数，为算法的时间复杂度)
通俗一点来说：时间复杂度就是一个算法中执行次数最多的那条语句的通式省略系数保留阶数最高的式子。
3.2 大o的渐进表示法
推导大o阶方法：
1、用常数1取代运行时间中的所有加法常数。若是一个算法的执行次数为确定的常数项，那么他的时间复杂度为o(1)
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大o阶。
举个例子：
int fun(int x)
{
int count = 0;
for (int i = 0; i < x; i )
{
for (int j = 0;j
以此算法为例，count ,执行次数为x*x次，那么它的时间复杂度为o(x^2)
void func1(int n)
{
int count = 0;
for (int i = 0; i < n; i)
{
for (int j = 0; j < n; j)
{
count;
}
}
for (int k = 0; k < 2 * n; k)
{
count;
}
int m = 10;
while (m--)
{
count;
}
此例中运行最多的代码段为 count，可以看出来它的执行次数为
f(n)=n*n 2*n 10；应用大o的渐进表示法，我们保留最高阶n*n=n^2,因此上述算法的时间复杂度为o(n^2)。
那么为什么是这样呢？因为当n无穷大时，除去最高阶对整个影响较大外，其他的常数及一次项对整体次数来说可忽略不计，时间复杂度取的是最差结果，因此对时间复杂度有了大o的渐进表示法。
定义
空间复杂度也是一个数学表达式，不是程序占用了多少字节的空间，而是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度计算规则基本跟实践复杂度类似，也使用大o渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
举例：
void bubblesort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; i)
{
if (a[i - 1] > a[i])
{
swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
上述算法中：n，exchange，i 在运行时要申请额外的空间来完成程序，因此额外申请了3个空间，是常数，因此用大o渐进表示法表示其空间复杂度就是o(1)
注：时间是累加的，一去不复返的；空间却是可以循环利用的。
这里我们用斐波那契数的递归算法来对比时间复杂度与空间复杂度