第2章 从算法的视角重新审视数学的概念
CHAPTER 2
第2章 从算法的视角重新审视数学的概念根据我们在第1章中对抽象算法设计与分析的讨论,算法的本质是预先给定的一组指令的排列组合;而算法分析是对指令的执行和存储单元的使用等离散现象的计数。源于算法的这一本质属性,我们需要熟练掌握相应的数学知识为抽象算法设计与分析服务。这些数学知识往往是我们已经学习过的,现在的重点是要从抽象算法设计与分析的角度来重新审视它们。
本章首先讨论算法设计与分析中常用的数学对象与数学性质。其次,为了进一步讨论算法代价的高低,我们引入函数渐近增长率(asymptotic growth rate)的概念。最后,我们从分析递归算法的角度讨论一类特殊递归方程的求解。