Date: 29 Dec 2014
在大学和研究生阶段都没修过算法，虽然对算法有所了解，但是很不系统。所以最近想系统地学习一下。这次学习的资料是 MIT 在 iTunes U 上的《算法导论》公开课程的视频和资料，课程是2005年录制的，听了两讲之后感觉并没有过时，毕竟算法的基础在最近几年并没多大的变化。这篇文章是关于算法分析的基础知识并不涉及具体的算法。
在算法分析中，我们通常要分析的是算法的运行时间，而且我们通常关注的是算法运行时间的上限（Upper bounds）。除了算法本身之外，运行时间还受到下列因素的影响：
例如，在排序算法中一个已经排好序的输入相对于一个随机排序的输入所需要的运行时间要短。
通常情况下，输入规模越大所需的运行时间也越长。
在输入规模一定的情况下算法所需的最长运行时间。
在输入规模一定的情况下，算法所需的运行时间的平均值。分析算法的平均情况需要对输入的分布（Distribution）进行假设，如正态分布等。
在输入规模一定的情况的算法所需的最短运行时间。这种情况一般是不需要进行分析的，因为这种分析结果只对于特定的输入才有效。
算法的运行时间同样会受到的计算机配置的影响，相同的算法在配置高的机器上的运行时间比在配置低的机器上的运行时间越短。而算法分析要尽量剔除由于机器配置不同给算法运行时间带来的影响，这就引入了算法分析中的核心思想（Big Idea):渐进式分析。这种分析的主要思想是观察算法的在输入规模 n 趋近与无穷大时，算法运行时间的增长（Growth）情况，而不是算法的绝对运行时间，这就剔除了由于机器配置给算法带来的影响。