【算法引论】张益新沈雁.pdf
算法引论 张益新沈雁编著
前言 序,调程序而已,其实不然。计算机科学虽然年轻,但它和数学、物理、化学、生物等历史悠 合NP就是一个典型例子。类似这样的难题长期以来困扰着计算机科学家,有可能还会困 拢很久。除了软件工程学,编译原理,操作系统,数据库原理外,算法分析与设计也是区别 专业软件工作者与其它人的一门重要课程.计算机科学的一个核心问题是算法理论。通过对常用的,有代表性的算法的研究,理 解并掌握算法设计的技术,掌握分析算法复杂度的能力,掌握算法评判的准则是算法分析 设计课程的目的。
第一章复杂度及其分析 早在电子计算机出现之前,对算法的研究就进行了多年,如欧几里德算法给出两数的 最大公因子、孙子算法给出最小公倍数。本世纪40年代以来,由于电子计算机的出现,使 许多原来难以处理的问题得以解决。这更进一步推动了对算法的研究,算法至今还是一个 非常活跃的研究领域.对于实际的问题要寻求并设计出求解的算法,不仅如此,还更应当分析算法的品性.81算法的复杂度 算法是一个出现频繁的术语。准确地说,问题的算法由有限个指令的序列组成。其中 每条指令都有明确的含义,每条指令的执行包含着有限的工作量.序列的执行会在有限时 间内停止下来,并给出对问题实例的解答。 