算法性能分析

一个程序所需要的资源越多，其复杂度越高。而计算机资源是时间和空间资源。因此算法的复杂性有时间复杂性和空间复杂性之分。

通常有两种衡量算法效率的方法：事后统计法和事前分析估算法。一般采用后者。

与算法执行相关的因素：

1. 算法所采用的“策略”
2. 算法所解决问题的“规模”
3. 编程所采用的“语言”
4. 编译程序产生的机器代码的质量
5. 执行算法的计算机的速度

后三条受到计算机硬件和软件的制约，仅需考虑前两条。问题规模n对不同的问题含义不同，对矩阵是阶数，对多项式运算是多项式项数，对图是顶点个数，对集合运算是集合中元素个数。

// n^2
for(i = 0; i < n; i++){   // n
  for(j = 0; j < n; i++){  }   // n^2
}

for (i=0;i<=n;++i)  // n
for (i=1;i<=n;++i)  // n+1

x = x+1;  // 1
for(j = 0; j < n; i++){ x = x+1;  }  // n

for(i = 0; i < n; i++){   // n
  for(j = 1; j < n; j*=2){  }   // log2n
}

复杂度与时间效率的关系：
c < log2n < n < nlog2n < n2 < n3 < 2n < 3n < n! （c是一个常量）
|--------------------------|--------------------------|-------------|
较好 一般 较差
其中c是一个常量，如果一个算法的复杂度为c 、 log2n 、n 、 nlog2n,那么这个算法时间效率比较高 ，如果是 2n , 3n ,n!,那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。

常见算法时间复杂度

算法性能衡量标准：

1. 稳定性

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。举个列子选择排序就是不稳定的。比如序列【5， 5， 3】第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面。

排序前：5-a,5-b,3-a
排序中!!不调整：5-a,5-b,3-a
排序中!!调整：3-a,5-b,5-a
排序后：3-a,5-b,5-a
-------------------
排序前：3-a,5-b,5-a
排序中!!不调整：3-a,5-b,5-a
排序后：3-a,5-b,5-a
-------------------
最终结果:3-a,5-b,5-a

2. 时间复杂度
   对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
3. 空间复杂度
   是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。