封面
版权信息
作者简介
数字版权声明
版权声明
献言
译者序
NOTE
算法并不仅仅是计算的方法，探究算法的过程反映出的是我们对这个世界的认知方法：是唯唯诺诺地将课本当做圣经，还是通过“实验——失败——再实验”循环的锤炼？数学是保证，数据是验证。
2022-02-25 20:09:46
NOTE
快速排序、霍夫曼编码、KMP等曾经熟悉的概念在你脑中是不是已经凋零成了一个个没有内涵的名词？是时候重新拾起它们了。无论是为手头的工作寻找线索，还是为下一份工作努力准备，这些算法基础知识都是你不能跳过的
2022-02-25 20:09:04
前言
NOTE
algs4.cs.princeton.edu
2022-02-28 22:05:16
NOTE
而本书则是专门为大学一、二年级学生设计的一学期教材，也是最新的基础入门书或从业者的参考书
2022-02-28 22:16:31
第1章 基础
NOTE
抽象数据类型（ADT）以进行模块化编程
2022-02-28 22:07:31
NOTE
抽象数据类型：背包、队列和栈
2022-02-28 22:11:38
NOTE
用数组、变长数组和链表实现了背包、队列和栈的API，它们是全书算法实现的起点和样板
2022-02-28 22:12:47
NOTE
科学式的，即先对性能提出假设，建立数学模型，然后用多种实验验证它们，必要时重复这个过程
2022-02-28 22:12:56
NOTE
用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。算法是计算机科学的基础，是这个领域研究的核心
2022-02-28 22:13:17
NOTE
优先队列、选举以及归并
2022-02-28 22:33:27
NOTE
基于事件的模拟、B树、后缀数组、最大流量问题以及其他高级主题
2022-02-28 22:32:54
1.1 基础编程模型
1.2 数据抽象
1.3 背包、队列和栈
1.4 算法分析
NOTE
1.4.2 观察
2022-04-21 19:05:04
NOTE
一般来说，问题的规模可以是输入的大小或是某个命令行参数的值。根据直觉，程序的运行时间应该随着问题规模的增长而变长，但我们每次在开发和运行一个程序时想问的问题都是运行时间的增长有多快。
2022-04-21 19:03:35
NOTE
因
2022-04-21 19:05:02
NOTE
重点研究如何更好地将问题规模和运行时间的关系量化
2022-04-21 19:04:52
NOTE
1.4.2.1 举例
2022-04-21 19:05:01
NOTE
你会发现自己进入了一个“预测——验证”的循环：它会快速打印出几行数据，但随即慢了下来。每当它打印出一行结果时，你都会开始琢磨它还需要多久才能打出下一行。当然，因为大家使用的计算机不同，你得到的实际运行时间很可能和我们的计算机得到的不一样。
2022-04-21 21:52:55
NOTE
程序在不同的计算机上的运行时间之比通常是一个常数
2022-04-21 21:53:10
NOTE
lg（T（N））= 3 lgN+ lga
2022-04-21 21:53:58
NOTE
T（N）= aN3
2022-04-21 21:54:09
NOTE
%7
2022-04-21 21:52:03
NOTE
对数图像中的直线等价于我们对数据符合公式T（N）=aNb的猜想。这种公式被称为幂次法则。
2022-04-21 21:54:54
NOTE
D. E. Knuth认为，尽管有许多复杂的因素影响着我们对程序的运行时间的理解，原则上我们仍然可能构造出一个数学模型来描述任意程序的运行时间。Knuth的基本见地很简单—— 一个程序运行的总时间主要和两点有关：❏执行每条语句的耗时；❏执行每条语句的频率。前者取决于计算机、Java编译器和操作系统，后者取决于程序本身和输入。如果对于程序的所有部分我们都知道了这些性质，可以将它们相乘并将程序中所有指令的成本相加得到总运行时间。
2022-04-21 21:55:17
NOTE
输入值是随机产生的，我们可以用概率分析得到该值的期望
2022-03-06 08:20:49
NOTE
我们常常使用约等于号（～）来忽略较小的项，从而大大简化我们所处理的数学公式。该符号使我们能够用近似的方式忽略公式中那些非常复杂但幂次较低，且对最终结果的贡献无关紧要的项
2022-03-06 08:23:50
NOTE
一般我们用到的近似方式都是g（N）～ af（N），其中f（N）=Nb（logN）c，其中a、b和c均为常数。我们将f（N）称为g（N）的增长的数量级（如表1.4.2所示）。我们一般不会指定底数，因为常数a能够弥补这些细节
2022-03-06 08:24:55
NOTE
执行最频繁的指令决定了程序执行的总时间——我们将这些指令称为程序的内循环
2022-03-06 08:27:43
1.5 案例研究：union-find算法
第2章 排序
2.1 初级排序算法
2.2 归并排序
2.3 快速排序
2.4 优先队列
2.5 应用
第3章 查找
3.1 符号表
NOTE
这些规则定义了关联数组的抽象形式。你可以将符号表想象成一个数组，键即索引，值即数组的元素。在一个一般的数组中，键就是整型的索引，我们用它来快速访问数组的内容；在一个关联数组（符号表）中，键可以是任意类型，但我们仍然可以用它来快速访问数组的内容。一些编程语言（非Java）直接支持程序员使用st[key]来代替st.get(key), st[key]=val来代替st.put(key, val)，其中key（键）和val（值）都可以是任意类型的对象。
2022-05-01 10:05:15
NOTE
删除的实现可以有两种方法
2022-05-03 15:47:20
NOTE
延时删除
2022-05-03 15:47:22
NOTE
即时删除
2022-05-03 15:47:48
NOTE
一种有序的泛型符号表的API
2022-05-03 17:58:51
NOTE
向下取整（floor）操作
2022-05-03 17:35:11
NOTE
和向上取整（ceiling）操作
2022-05-03 17:35:14
NOTE
，请确认对于0到size()-1的所有i都有irank(select(i))，且所有的键都满足keyselect(rank(key))。
2022-05-03 17:36:00
NOTE
约定所有有序符号表API的实现都含有如表3.1.6所示的方法
2022-05-03 17:37:37
NOTE
任何一种Comparable类型的两个值a和b都要保证(a.compareTo(b)==0)和a.equals(b)的返回值相同。
2022-05-03 17:38:30
NOTE
因为将它们作为练习能够更好地检验你对实现背后的数据结构的理解程度
2022-05-03 17:40:48
NOTE
这是一种字典
2022-05-03 17:44:11
NOTE
Leipzig Corpora Collection的数据库（leipzig1M.txt）
2022-05-03 17:44:47
NOTE
具体会打印出哪一个取决于符号表的具体实现
2022-05-03 17:45:15
NOTE
st.keys()
2022-05-03 17:57:18
NOTE
我们的实现能够在一张用多次get()和put()方法构造出的巨型符号表中进行大量的get()操作吗？
2022-05-03 17:58:26
NOTE
这里我们将size()、keys()和即时型的delete()方法留做练习
2022-05-03 18:00:07
NOTE
对于FrequencyCounter，最常见的情形是虽然查找和插入的使用模式是不可预测的，但它们的使用肯定不是随机的。因此我们主要研究最坏情况下的性能
2022-05-03 18:00:41
NOTE
命中的查找在最坏情况下需要N次比较。特别地，向一个空表中插入N个不同的键需要～N2/2次比较。
2022-05-03 18:03:05
3.2 二叉查找树
3.3 平衡查找树
3.4 散列表
3.5 应用
NOTE
逗号分隔的格式（及类似格式）常用于存储网络信息
2022-03-07 12:16:32
第4章 图
4.1 无向图
NOTE
图是由一组顶点和一组能够将两个顶点相连的边组成的
2023-01-03 10:27:46
NOTE
这种直觉有时也可能会误导我们，因为图的定义和绘出的图像是无关的
2023-01-03 10:27:39
NOTE
❏自环，即一条连接一个顶点和其自身的边；❏连接同一对顶点的两条边称为平行边。
2023-01-03 10:28:02
NOTE
数学家常常将含有平行边的图称为多重图，而将没有平行边或自环的图称为简单图
2023-01-03 10:28:13
NOTE
当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并称这条边依附于这两个顶点。某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。
2023-01-03 10:30:23
NOTE
如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这幅图是连通图。一幅非连通的图由若干连通的部分组成，它们都是其极大连通子图
2023-01-03 10:31:26
NOTE
无环图是一种不包含环的图。我们将要学习的几个算法就是要找出一幅图中满足一定条件的无环子图。我们还需要一些术语来表示这些结构。
2023-01-03 10:32:18
NOTE
树是一幅无环连通图。互不相连的树组成的集合称为森林。连通图的生成树是它的一幅子图，它含有图中的所有顶点且是一棵树。图的生成树森林是它的所有连通子图的生成树的集合，参见图4.1.4和图4.1.5。
2023-01-03 10:32:33
NOTE
当且仅当一幅含有V个结点的图G满足下列5个条件之一时，它就是一棵树：❏G有V-1条边且不含有环；❏G有V-1条边且是连通的；❏G是连通的，但删除任意一条边都会使它不再连通；❏G是无环图，但添加任意一条边都会产生一条环；❏G中的任意一对顶点之间仅存在一条简单路径。
2023-01-05 02:25:13