无论是设计算法还是应用算法，都必须理解该算法的性能。 我们通常最关心算法的运行速度，但在某些情况下，我们也必须关心算法对内存空间的要求。
最坏情况分析法：评价算法性能常用的三种情况是最优情况、平均情况和最坏情况。 但是，一般来说，我关心最坏情况下算法的性能。 理由如下。
许多算法在最坏的情况下需要相当长的时间才能运行。 考虑算法在最佳状态下的性能没有什么意义。 因为许多算法在最佳状态下工作方式相同。 分析算法平均情况下的性能往往不是那么容易的。 甚至很难将什么样的状况称为“平均状况”。 最坏的情况下，它会告诉你算法的性能上限。 虽然以最坏的情况作为许多算法性能的度量，但也有例外，有时用平均的情况来评价算法的性能。
o表示法： o表示法是用于表示算法性能的最普通、最正式的表示法。 简单的规则如下
常数项可以忽略。 常数项用o(1)表示。 关于几个常数c，正式地表示为o(c )=o ) )1)。 常数因子可以忽略。 对于一些常数c，正式表示为o(CT )=co ) t )=o ) t )。 加法取最大值。 正是标记为o(T1 ) o ) T2 )=O ) T1T2 )=max ) o ) T1 )，o ) T2 )。 一旦计算了乘法的结果，就只考虑高阶项因子就可以了。 正式表示为o(t1 ) o ) t2 )=o ) O(T2 )。 典型复杂性： o(1) :从数据集检索第一个元素。 O(LGN ) :将一个数据集分成两半，每一半再分成两半，按顺序同样处理。 O(N ) :一个数据集o ) NLGN )的遍历。 将一个数据集分割成一半，然后按分割后的一半再分割成一半。 在这个过程中同时遍历一半的数据。 O(N )2) :在遍历一个数据集合中的每个元素的同时，遍历相同数量级的另一个数据集合。 o(2^n ) :为一个数据集生成所有可能的子集。 o(n )！为一个数据集生成所有可能的数组组合。复杂度从低到高排列：
o(1) o ) LGn ) o ) n ) o(nlgn ) o ) n^2LGn ) o ) n^3) o )2^n ) o )3^n ) o ) n ) n ) n！ ）