【算法】算法简介
相似文章推荐：
- 八种常见数据结构介绍
- 七大查找算法的理解与实现
- 路径规划中的Dijkstra(狄克斯特拉)与A星算法
- 八大经典排序算法的理解、动图演示和C++方法实现
1. 定义
算法（Algorithm）：是指用来操作数据、解决程序问题的一组方法。对一定规范的输入，在有限的时间内获得所要求的输出。
一个算法的优劣可以用空间复杂度和时间复杂度来衡量。
2. 时间复杂度
按照常理来说，一个算法的时间复杂度用程序的一次执行时间来表示，这种方式有以下弊端。
- 容易受运行环境（不同测试机器）的影响；
- 对测试数据的规模也有很大的关系。
- 在写算法的过程中，算法可能没有办法完整运行。
大O表示法
大O表示法：即T(n) = O(f(n))。
先举例说明：
for(i=1; i<=n; ++i)
{//执行一次j = i;//执行n次j++;//执行n次
}
根据上式的注释，假设每一行执行时间为1，则这个算法执行时间为1+2n，当n很大的时候，这里的1和2就没有意义了。所以它的时间复杂度就为T(n) = O(n)。
常用的时间复杂度量级有（从上至下依次的时间复杂度越来越大，执行的效率越来越低）：
- 常数阶O(1)
- 对数阶O(logN)
- 线性阶O(n)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)
常数阶O(1)
没有循环等复杂结构，那么这个代码的时间复杂度都是O(1):
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
线性阶O(n)
循环代码会执行n遍：
for(i=1; i<=n; ++i)
{j = i;j++;
}
对数阶O(logN)
int i = 1;
while(i<n)
{i = i * 2;
}
假设循环执行x次后，i就大于2了，那么2的x次方等于n，那么x = log2^n。
所以代码循环了log2^n次，它的时间复杂度为O(logn)
线性对数阶O(nlogN)
其实就是对数阶的外边再加一层循环：
for(m=1; m<n; m++)
{i = 1;while(i<n){i = i * 2;}
}
平方阶O(n²)
双层for循环就是n的平方了：
for(x=1; i<=n; x++)
{for(i=1; i<=n; i++){j = i;j++;}
}
下列代码的时间复杂度为O(m*n):
for(x=1; i<=m; x++)
{for(i=1; i<=n; i++){j = i;j++;}
}
其他时间复杂度参考上面的方式理解。
3. 空间复杂度
既然时间复杂度不是用计算程序具体耗时，那么空间复杂度也不是用来计算程序实际占用的空间。
空间复杂度比较常用的有：O(1)、O(n)、O(n²)
空间复杂度O(1)
算法执行所需的空间不随某个变量n的大小而变化：
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。
空间复杂度O(n)
int[] m = new int[n]
for(i=1; i<=n; ++i)
{j = i;j++;
}
这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n).
【算法】算法简介
相似文章推荐：
- 八种常见数据结构介绍
- 七大查找算法的理解与实现
- 路径规划中的Dijkstra(狄克斯特拉)与A星算法
- 八大经典排序算法的理解、动图演示和C++方法实现
1. 定义
算法（Algorithm）：是指用来操作数据、解决程序问题的一组方法。对一定规范的输入，在有限的时间内获得所要求的输出。
一个算法的优劣可以用空间复杂度和时间复杂度来衡量。
2. 时间复杂度
按照常理来说，一个算法的时间复杂度用程序的一次执行时间来表示，这种方式有以下弊端。
- 容易受运行环境（不同测试机器）的影响；
- 对测试数据的规模也有很大的关系。
- 在写算法的过程中，算法可能没有办法完整运行。
大O表示法
大O表示法：即T(n) = O(f(n))。
先举例说明：
for(i=1; i<=n; ++i)
{//执行一次j = i;//执行n次j++;//执行n次
}
根据上式的注释，假设每一行执行时间为1，则这个算法执行时间为1+2n，当n很大的时候，这里的1和2就没有意义了。所以它的时间复杂度就为T(n) = O(n)。
常用的时间复杂度量级有（从上至下依次的时间复杂度越来越大，执行的效率越来越低）：
- 常数阶O(1)
- 对数阶O(logN)
- 线性阶O(n)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)
常数阶O(1)
没有循环等复杂结构，那么这个代码的时间复杂度都是O(1):
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
线性阶O(n)
循环代码会执行n遍：
for(i=1; i<=n; ++i)
{j = i;j++;
}
对数阶O(logN)
int i = 1;
while(i<n)
{i = i * 2;
}
假设循环执行x次后，i就大于2了，那么2的x次方等于n，那么x = log2^n。
所以代码循环了log2^n次，它的时间复杂度为O(logn)
线性对数阶O(nlogN)
其实就是对数阶的外边再加一层循环：
for(m=1; m<n; m++)
{i = 1;while(i<n){i = i * 2;}
}
平方阶O(n²)
双层for循环就是n的平方了：
for(x=1; i<=n; x++)
{for(i=1; i<=n; i++){j = i;j++;}
}
下列代码的时间复杂度为O(m*n):
for(x=1; i<=m; x++)
{for(i=1; i<=n; i++){j = i;j++;}
}
其他时间复杂度参考上面的方式理解。
3. 空间复杂度
既然时间复杂度不是用计算程序具体耗时，那么空间复杂度也不是用来计算程序实际占用的空间。
空间复杂度比较常用的有：O(1)、O(n)、O(n²)
空间复杂度O(1)
算法执行所需的空间不随某个变量n的大小而变化：
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。
空间复杂度O(n)
int[] m = new int[n]
for(i=1; i<=n; ++i)
{j = i;j++;
}
这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n).