《算法技术手册》一2.3.1 最坏情况

2.3.1 最坏情况

对于任一特定值n，算法或者程序在处理所有规模为n的样本时的执行时间可能会发生巨大的变化。对于一个给定的程序和一个给定的值，最坏的执行时间就是处理所有规模为n的数据所需要的最长执行时间。
之所以关注算法的最坏情况，是因为它通常是最容易分析的情况。此外，它还能够说明程序在各种场景下到底会有多慢。
更正式地说，如果Sn是所有规模为n的问题样本si构成的集合，t()代表算法对于每一个问题样本所需要的执行时间，那么算法在最坏情况下的执行时间为：t(si)对于所有si∈Sn的最大值。我们将Sn在最坏情况下的性能记作Twc(n)。Twc(n)的增长率定义了算法在最坏情况下的复杂度。
一般来说，通过计算每一份数据si来判定算法在哪份数据上表现最坏，这种做法是不切实际的——没有足够的资源。相反，算法分析人员会精心设计出能让算法的性能落入最坏情况的问题样本。