概述
算法（Algorithm）：是指用来操作数据、解决问题的一组方法。对于同一问题，使用不同的算法，得到最终的结果是一样的。但在过程中消耗的资源和时间却有很大的区别。
我们通过时间和空间两个维度去考量算法之间的优劣。
-
时间维度：是指执行当前算法所消耗的时间，我们通常叫做
时间复杂度，可以使用大O表示法。 -
空间维度：是指执行当前算法所需要占用多少内存空间，我们通常叫做
空间复杂度。
因此我们判定一个算法的效率主要就是看他执行过程的时间复杂度和空间复杂度情况。然后时间和空间却是像鱼和熊掌，不可兼得。那么我们就需要从中去一个平衡点，或者直接用空间来换时间（毕竟当今技术发展情况空间很廉价）。
1. 时间复杂度
算法的时间复杂度，并不是用来实际计算算法执行时间的。我们可以通过两种方式来对算法的效率来进行计算或估算。
事后统计方法：通过设计好的测试程序和数据，在执行不同算法时，利用计算机计时器进行时间的记录，最后将记录结果进行比较。
这种方式显然是有大的缺陷的：
1. 受不同机器性能影响，结果差异很大；
2. 测试时，使用的数据规模不同，对结果的影响也会很大，算法A在数据规模小时效果不一定优于算法B，但在数据规模庞大时，可能会有很好的表现；
3. 事先设定好的测试程序，对不同算法的性能不一定能达到最优表现；事前分析统计方法：在计算机程序编写前，依据统计方法对算法进行估算。（大O记法）
抛开计算机硬件与软件有关的因素，算法的效率主要依赖于两点：
1. 算法采用的策略、方案；
2. 数据的输入规模（输入量）；
时间复杂度计算方法
一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。
显然，由此算法时间复杂度的定义可知，我们的三个求和算法的时间复杂度分别为O(1)，O(n)，O(n²)。
大O表示法
- 用常数1代替运行时间中的所有加法常数；O(5) ==> O(1)
- 修改后的函数中，只保留最高阶项；O(n² + n + 3) ==> O(n²)
- 去除最高阶项的系数；O(5n³ + 3n² +2) ==> O(n³)
常见的时间复杂度量级
- 常数阶O(1)：除去所有对算法结果本身无任何影响的操作，只针对算法实际有效项计算时间复杂度。
int sum = 0, n = 100;
printf("当前："+sum+","+n); //对算法结果无任何影响
sum = (1+n)*n/2;
- 线性阶O(n)：一般含有非嵌套循环涉及线性阶，线性阶就是随着问题规模n的扩大，对应计算次数呈直线增长。
int i , n = 100, sum = 0;
for( i=0; i < n; i++ )
{
sum = sum + i;
}
-
平方阶O(n²) / 立方阶O(n³)：外层循环每执行一次，内层循环就执行100次，那总共程序想要从这两个循环出来，需要执行100*100次，也就是n的平方
O(n²)。
如果有三个这样的嵌套循环也就是n的立方O(n³)，
int i, j, n = 100;
for( i=0; i < n; i++ )
{
for( j=0; j < n; j++ )
{
printf("i=" + i + "；j=" + j + "；n=" + n);
}
}
推论： K次方阶O(n^k)
-
对数阶O(logN)：由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于或等于n，则会退出循环。
于是由2^x = n得到x = log(2)n，所以这个循环的时间复杂度为O(logn)。
int i = 1, n = 100;
while( i < n )
{
i = i * 2;
}
线性对数阶O(nlogN)：
指数阶(2^n)：
2. 空间复杂度
算法的空间复杂度，也并不是用来计算程序实际占用的空间的。
空间复杂度是对一个算法运行过程中临时占荣存储空间大小的一个度量，同样反映的是一个趋势，我们用S(n)来定义。
空间复杂度比较常用的有：O(1)、O(n)
- O(1)： 算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)
-
O(n)：
数组m数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
``