算法效率分析基础
算法效率分析是对一个算法需要多少计算时间和存储空间作定量的分析。时间是非常重要的，不是所有能计算的都有价值，不是所有有价值的都能被计算。这章节将介绍算法效率分析的基础知识，包括算法效率分析框架、算法效率的表示符号、非递归算法的效率分析、递归算法的效率分析、算法的经验分析等。
算法效率分析框架
算法效率分析框架是指对算法的时间效率和空间效率的度量。时间效率是指算法需要多少计算时间，空间效率是指算法需要多少存储空间。算法效率分析框架包括输入规模度量、运行时间的度量单位、增长次数、算法的最优、最差和平均效率等几个方面。
输入规模度量是指算法的时间效率和空间效率都用输入规模的函数进行度量。输入规模 n 是一个参数，用于研究算法的效率。选择输入规模的合适量度，要受到所讨论算法的操作细节影响。
运行时间的度量单位是指用算法的基本操作（算法中最重要的操作）的执行次数来度量算法的时间效率。基本操作通常是算法最内层循环中最费时的操作。算法运行时间的估计：T(n) ≈ copC(n)，其中 n 是该算法的输入规模，cop 是特定计算机上一个算法基本操作的执行时间，C(n) 是该算法需要执行的基本操作的次数。
增长次数是指小规模输入在运行时间上的差别不足以将高效的算法和低效的算法区分开来。一个需要指数级操作次数的算法只能用来解决规模非常小的问题。
算法的最优、最差和平均效率是指在输入规模为 n 时，算法在最坏情况下的效率、最优情况下的效率和“典型”或“随机”输入的情况下的行为（效率）。摊销效率是指对于同样的数据结构执行多次操作，然后分摊到每一次上。
渐进符号是指对算法效率的主要指标是基本操作次数的增长次数。为了对这些增长次数进行比较和归类，计算机科学家们使用了 3 种符号：O（读“ O” ），Ω（读” omega” ），Θ（读” theta” ）。O 是上界，Ω 是下界，Θ 是近似。
符号 O 是指对于足够大的 n，t(n) 的上界由 g(n) 的常数倍来确定，即：t(n) ≤ cg(n)，c 为常数。
符号 Ω 是指对于足够大的 n，t(n) 的下界由 g(n) 的常数倍来确定，即：t(n) ≥ cg(n)，c 为常数。
符号 Θ 是指对于足够大的 n，t(n) 的近似值由 g(n) 的常数倍来确定，即：t(n) ≈ cg(n)，c 为常数。
本章节介绍了算法效率分析的基础知识，包括算法效率分析框架、算法效率的表示符号、非递归算法的效率分析、递归算法的效率分析、算法的经验分析等，为后续学习算法设计和分析奠定了基础。
