*文中代码字体版权说明

内容提要

本书以程序设计为基础，数据结构为工具，六大核心算法为目标，系统地介绍了算法设计中典型问题的求解过程。

全书内容包括算法设计与分析基础、递归算法、分治算法、贪心算法、动态规划算法、回溯算法、分支限界算法、实验指导。六大核心算法后都配有典型问题的C++代码实现，并结合实验指导辅助读者进行算法实践训练。

本书结构清晰，内容翔实，通俗易懂，深入浅出，兼顾理论和实践，可作为高等学校计算机或软件工程专业学生的教材，也可作为工程技术人员的参考书。

前言

“算法设计与分析”是计算机科学的核心问题，该课程已经成为计算机科学与技术专业及软件工程专业课程体系中一门重要的必修课。本课程目的是通过对计算机领域的许多常见问题和有代表性算法的学习和研究，使读者了解并掌握算法设计的一些主要方法，提高分析问题的基本技能，达到独立设计算法和分析其复杂度的水平。

全书共7章。第1章介绍算法的基本概念，并对分析算法复杂度的准则及本书用到的基本数据结构的知识做了简要的介绍。第2章至第7章分别介绍常用的算法设计方法，它们分别是递归算法、分治算法、贪心算法、动态规划算法、回溯算法和分支限界算法。本书选取具有代表性的问题，讲解这些经典算法的思路。另外，为了便于读者掌握各类基本算法，书后附有算法应用的练习。

本书主要体现了如下特点。

（1）以算法设计为主线来组织素材，针对具体问题类，深入分析了算法设计思路、设计步骤、算法描述及算法复杂度等；从问题建模、算法设计与分析、算法改进等方面给出适当的描述，在理论上为实际问题的算法设计与分析提供了清晰、整体的思路和方法。与常见的算法和数据结构教材有所不同，本书并没有过多关注细节，算法描述采用伪码，力求突出对问题本身的分析和求解方法的阐述。

（2）在本书内容的组织上，不仅围绕问题类展开，将不同方法用于求解同一问题并进行讲解，便于读者把握问题分析的发展脉络，还通过比较分布在不同章节、求解同一问题的不同算法，让读者了解算法的设计过程。同时，在各章中还将同一算法的设计方法和设计策略用于不同问题的求解，更便于读者体会、掌握算法设计的思路。

（3）本书的素材来自作者多年的教学积淀，选材适当，组织合理，先引入基本概念和数学基础知识，然后进行算法设计与分析的核心内容讲解。在叙述中不但注意理论的严谨，也精选了大量生动有趣的例子，每章都配有难度适当的练习，适合教学使用。

本书框架由多位教学一线的老师共同讨论制定。参与编写的老师分工如下：杨崇艳编写第1章，张晓霞编写第2章、第5章，王幸民编写第3章、第4章，闫鹏飞编写第6章和实验指导，薛晋东编写第7章。

在编写的过程中参考了国内外多种版本的算法设计与分析以及计算复杂性方面的教材、论文和专著，从中吸取了一些优秀的思路和素材，在此一并向有关作者致谢。

编者

2018年1月

第1章

算法设计与分析基础

计算机系统中的任何软件都是按一个个特定的算法来予以实现的。用什么方法来设计算法，如何判定一个算法的性能，设计的算法需要多少运行时间、多少存储空间，这些问题都是在开发一个软件时必须考虑的。算法性能的好坏，直接决定了软件性能的优劣。

本章将主要介绍算法、算法设计、算法分析的基本概念，以及常见重要问题的类型和常用算法的设计方法。

1.1

算法概述

1.1.1

什么是算法

算法研究是计算机科学的主要任务之一。利用计算机解决一个实际问题时，首先是选择一个合适的数学模型表示问题，以便抽象出问题的本质特征，其次就是寻找一种算法，作为问题的一种解法。那么什么是算法，算法有什么基本特征，算法的组成有哪些？

1. 算法的定义

算法是解题方案的准确而完整的描述，也就是解题的方法和步骤。下面举两个例子来说明算法。