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