算法(4th ed)(1):基础

阅读数:22 2019 年 10 月 26 日 09:58

算法(4th ed)(1):基础

本书的目的是研究多种重要而实用的算法,即适合用计算机实现的解决问题的方法。和算法关系最紧密的是数据结构,即便于算法操作的组织数据的方法。本章介绍的就是学习算法和数据结构所需要的基本工具。

首先要介绍的是我们的基础编程模型。本书中的程序只用到了 Java 语言的一小部分,以及我们自己编写的用于封装输入输出以及统计的一些库。1.1 节总结了相关的语法、语言特性和书中将会用到的库。

接下来我们的重点是数据抽象并定义抽象数据类型(ADT)以进行模块化编程。在 1.2 节中我们介绍了用 Java 实现抽象数据类型的过程,包括定义它的应用程序编程接口(API)然后通过 Java 的类机制来实现它以供各种用例使用。

之后,作为重要而实用的例子,我们将学习三种基础的抽象数据类型:背包、队列。1.3 节用数组、变长数组和链表实现了背包、队列和栈的 API,它们是全书算法实现的起点和样板。

性能是算法研究的一个核心问题。1.4 节描述了分析算法性能的方法。我们的基本做法是科学式的,即先对性能提出假设,建立数学模型,然后用多种实验验证它们,必要时重复这个过程。

我们用一个连通性问题作为例子结束本章,它的解法所用到的算法和数据结构可以实现经典的 union-find 抽象数据结构。

评论

发布