算法（第4版）

Robert Sedgewick Kevin Wayne

译者序

  • 算法并不仅仅是计算的方法，探究算法的过程反映出的是我们对这个世界的认知方法：是唯唯诺诺地将课本当做圣经，还是通过“实验——失败——再实验”循环的锤炼？数学是保证，数据是验证。
  • 所有的算法都是先有API，再有实现，之后是证明，最后是数据。这种先接口后实现、强调测试的做法，无疑是在工作中摸爬滚打多年的程序员最熟悉的。
  • 没有介绍动态规划这样重要的思想

前言

  • algs4.cs.princeton.edu
  • 这本书意在接续我们的一本基础教材《Java程序设计：一种跨学科的方法》，那本书对计算机领域做了概括性介绍。
  • Sedgewick的《C算法（第3版）》、《C++算法（第3版）》、《Java算法（第3版）》

第1章 基础

  • 和算法关系最紧密的是数据结构，即便于算法操作的组织数据的方法。
  • 数据抽象并定义抽象数据类型（ADT）以进行模块化编程
  • 应用程序编程接口（API）
  • 背包、队列和栈
  • 性能是算法研究的一个核心问题。
  • 在计算机科学领域，我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。
  • 要定义一个算法，我们可以用自然语言描述解决某个问题的过程或是编写一段程序来实现这个过程。
  • 每种算法都是适合于在任何计算机上用任何编程语言实现的方法。
  • 在本书中，我们的观点是数据结构是算法的副产品或是结果，因此要理解算法必须学习数据结构。
  • 但是对于大型问题（或者是需要解决大量小型问题的应用），我们就需要设计能够有效利用时间和空间的方法了。
  • 学习算法的主要原因是它们能节约非常多的资源，甚至能够让我们完成一些本不可能完成的任务。
  • 在编写庞大或者复杂的程序时，理解和定义问题、控制问题的复杂度和将其分解为更容易解决的子问题需要大量的工作
  • 实现这些基础算法的简化版本有助于我们更好地理解、使用和优化它们在库中的高级版本
  • 为一项任务选择最合适的算法是困难的，这可能会需要复杂的数学分析。计算机科学中研究这种问题的分支叫做算法分析。
  • 插入排序、选择排序、希尔排序、快速排序、归并排序和堆排序
  • 二叉查找树、平衡查找树和散列表
  • 深度优先搜索、广度优先搜索、连通性问题以及若干其他算法和应用，包括Kruskal和Prim的最小生成树算法、Dijkstra和Bellman-Ford的最短路径算法。

1.1 基础编程模型

  • ❏程序是对算法精确、优雅和完全的描述；❏可以通过运行程序来学习算法的各种性质；❏可以在应用程序中直接使用这些算法。
  • 我们把描述和实现算法所用到的语言特性、软件库和操作系统特性总称为基础编程模型。
  • 我们会使用六种语句：声明、赋值、条件、循环、调用和返回。
  • 要执行一个Java程序，首先需要用javac命令编译它，然后再用java命令运行它。
  • 关键性质是运算产生的数据的数据类型和参与运算的数据的数据类型是相同的。这也意味着我们
  • 运算符＊和/（以及%）的优先级高于+和-（优先级越高，越早运算）；在逻辑运算符中，！拥有最高优先级，之后是&&，接下来是||。
  • 如果不会损失信息，数值会被自动提升为高级的数据类型。
  • 转换指的是在表达式中把类型名放在括号里将其后的值转换为括号中的类型
  • 将浮点型转换为整型将会截断小数部分而非四舍五入
  • Java是一种强类型的语言，因为Java编译器会检查类型的一致性
  • 数组名表示的是整个数组——如果我们将一个数组变量赋予另一个变量，那么两个变量将会指向同一个数组
  • 如果你是想将数组复制一份，那么应该声明、创建并初始化一个新的数组，然后将原数组中的元素值挨个复制到新数组
  • 方法只能返回一个值，但可以包含多个返回语句
  • 递归调用的父问题和尝试解决的子问题之间不应该有交集。
  • API的目的是将调用和实现分离
  • 将这些结合起来，将一个程序的输出重定向为另一个程序的输入叫做管道：
  • 简单地说，数据抽象的主要思想是鼓励程序定义自己的数据类型（一系列值和对这些值的操作），而不仅仅是那些操作预定义的数据类型的静态方法。

1.2 数据抽象

  • 数据类型指的是一组值和一组对这些值的操作的集合
  • Java编程的基础主要是使用class关键字构造被称为引用类型的数据类型。
  • 抽象数据类型（ADT）是一种能够对使用者隐藏数据表示的数据类型。
  • 所有对象都有三大重要特性：状态、标识和行为
  • 静态方法的主要作用是实现函数；非静态（实例）方法的主要作用是实现数据类型的操作。
  • 在Java中，所有非原始数据类型的值都是对象。

1.3 背包、队列和栈

  • 集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据
  • 自动将一个原始数据类型转换为一个封装类型被称为自动装箱
  • 背包是一种不支持从中删除元素的集合数据类型
  • 使用Bag可以说明元素的处理顺序不重要
  • 先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型
  • 下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型
  • Dijkstra的双栈算术表达式求值算法
  • 由于某些历史和技术原因（不在本书讲解范围之内），创建泛型数组在Java中是不允许的。我们需要使用类型转换：
  • 链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。
  • 顺序存储和链式存储

1.4 算法分析

  • 再多的实验也不一定能够证明我是对的，但只需要一个实验就能证明我是错的
  • ❏执行每条语句的耗时； ❏执行每条语句的频率。

2.1 初级排序算法

  • 除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间来存储另一份数组副本的其他排序算法。
  • 这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。
  • 对于长度为N的数组，选择排序需要大约N2/2次比较和N次交换。
  • 运行时间和输入无关
  • 插入排序对于部分有序的数组十分高效，也很适合小规模数组。
  • 交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
  • 希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。

2.3 快速排序

  • 而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了

4.1 无向图

  • 数学家常常将含有平行边的图称为多重图，而将没有平行边或自环的图称为简单图。
  • 如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这幅图是连通图
  • 图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例
  • 二分图是一种能够将所有结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分
klib.me