算法的概述

算法分析：

解决同一问题的算法可以有多种。 我们希望从中选出最优的算法，效率高或者存储空间小。为此，需要对算法进行评估，分析。

通常考虑两个度量：

1、 时间复杂度：算法运行时需要的总步数，通常是问题规模的函数。

•  以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况时间复杂度
•  以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度
• 最坏情况时间复杂度和平均情况时间复杂度通称为时间复杂度

2、 空间复杂度：算法执行时所占用的存储空间，通常是问题规模的函数。

一个算法在执行期间所需要的存储空间量包括以下部分：

• 程序代码所占用的空间；
• 输入数据所占用的空间；
• 辅助变量所占用的空间；

估算算法空间复杂度时，一般只分析辅助变量所占用的空间。

常见的复杂度按数量级递增排列依次为：

常数O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),多项式阶O(nC),指数阶O(Cn)