算法性能分析

评价算法的标准：

一般来说，评价一个算法的好坏就是看它的时间和空间，因为空间现在的内存都很大，考虑的比较少，我们主要考虑算法的时间复杂度怎样进行度量。

问题的规模N定义：

问题规模N与该算法在运行时所占的空间S与所耗费的时间T有关。

对不同的问题其含义不同：
对矩阵是阶数；
对多项式运算是多项式项数；
对图是顶点个数；
对集合运算是集合中元素个数。

衡量算法效率的方法：

（1）事后统计法
缺点：1.必须执行程序 2.其他因素掩盖算法本质
（2)事前统计法
我们更倾向于事前统计法。

和算法执行时间有关的因素：

（1）算法选用的策略
（2）问题的规模
（3）编写程序的语言
（4）编译程序产生的机器代码的质量
（5）计算机执行指令的速度

算法执行时间：

一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。
分析：
算法执行时间并不是程序实际执行的时间，而是算法中所有基本操作语句（原操作）的执行时间。

语句频度：语句在一个算法中重复执行的次数。

算法的时间复杂度

算法的时间复杂度：T(n) = O( f(n) ) ，f(n)就是算法中语句执行的总次数。所以只要我们知道了算法中所有语句执行的总次数，就知道了时间复杂度。

1. x=x+1 ; 时间复杂度为O(1)，称为常量阶；
2. for (i=1; i<=n; i++) x=x+1; 时间复杂度为O(n)，称为线性阶；
3. for (i=1; i<=n; i++) for(j=1; j<=n; j++) x=x+1; 时间复杂度为O(n²)，称为平方阶

常用的时间复杂度频率表：

网课笔记，如有错误欢迎指正(●’◡’●)