第2章 算法效率分析基础 主要内容： 2.1 分析框架 2.2 渐进符号和基本效率类型 2.3 非递归算法的数学分析 2.4 递归算法的数学分析2.1 算法分析的基本框架 一般而言，对于一个算法的分析主要是 对算法效率的分析，包括了衡量其运行 速度的时间效率以及衡量算法运行需要 占用空间大小的空间效率。对于早期的 计算机来说，时间与空间都是极其珍贵 的资源。半个世纪以来，硬件技术的发 展大大提高了计算机的存储容量，使得 存储容量的局限性对于算法的影响大大 降低了。但时间效率并没有得到相同程 度的提高。因此，算法的时间效率是算 法分析中的关键部分。 2.1.1 输入规模的度量 一个显而易见的事实是：大部分算 法的执行时间随着输入量的增加而 增大。例如在对一个数组进行排序 时，数组越大，排序需要的时间就 越长。因此从逻辑上来说，算法的 效率应该是输入量的函数。 2.1.2 运行时间的度量单位 算法时间包括了编译该算法的时间以 及运行该算法的时间。因此衡量算法时 间的单位很自然的会想到用“秒”、“毫秒 ”等实际的时间单位。这对于算法的测试 者而言是很直观的，但是存在的问题是 ：编译算法的时间
