普林斯顿算法讲义（一）（3）

普林斯顿算法讲义（一）(2)https://developer.aliyun.com/article/1484168

1. 复制一个栈。 为链表实现的 Stack.java 创建一个新的构造函数，使得 Stack t = new Stack(s) 使 t 引用栈 s 的一个新且独立的副本。
   递归解决方案: 为从给定 Node 开始的链表创建一个复制构造函数，并使用它来创建新的栈。

Node(Node x) {
   item = x.item;
   if (x.next != null) next = new Node(x.next);
}
public Stack(Stack<Item> s) { first = new Node(s.first); }

1. 非递归解决方案: 为单个 Node 对象创建一个复制构造函数。

Node(Node x) { this.item = x.item; this.next = x.next; }
public Stack(Stack<Item> s) {
   if (s.first != null) {
      first = new Node(s.first);
      for (Node x = first; x.next != null; x = x.next)
         x.next = new Node(x.next);
   }
}

1. 栈的可生成性。 假设我们有一个混合 push 和 pop 操作的序列，就像我们的测试栈客户端一样，其中按顺序 0、1、…、N-1（push 指令）与 N 个减号（pop 指令）交错。设计一个算法，确定混合序列是否会导致栈下溢。 （您只能使用与 N 无关的空间量 - 不能将整数存储在数据结构中。）设计一个线性时间算法，确定给定排列是否可以由我们的测试客户端生成输出（取决于 pop 操作发生的位置）。
   解决方案。 只有存在整数 k，使得前 k 个 pop 操作发生在前 k 个 push 操作之前，栈才会下溢。
   如果可以生成给定的排列，那么它将唯一生成如下：如果排列中的下一个整数在栈的顶部，则弹出它；否则，将输入序列中的下一个整数推送到栈上（或者如果已经推送了 N-1，则停止）。 只有在终止时栈为空，排列才能生成。
   
2. 栈可生成的禁止三元组。 (R. Tarjan) 证明排列可以由栈生成（如前一个问题中所述），当且仅当它没有 禁止的三元组 (a, b, c)，其中 a < b < c，c 第一，a 第二，b 第三（可能在 c 和 a 之间以及 a 和 b 之间有其他插入的整数）。
   部分解决方案。 假设存在一个禁止的三元组（a，b，c）。 在 a 和 b 之前弹出项 c，但在 c 之前推入 a 和 b。 因此，当推入 c 时，a 和 b 都在栈上。 因此，在弹出 b 之前，a 不能被弹出。
   
3. 可连接的队列、栈或 steque。 添加一个额外的 连接 操作，（破坏性地）连接两个队列、栈或 steques。 提示: 使用循环链表，保持指向最后一项的指针。
   
4. 快速失败的迭代器。 修改 Stack.java 中的迭代器代码，如果客户端在迭代期间修改集合（通过 push() 或 pop()）则立即抛出 java.util.ConcurrentModificationException。
   解决方案: 维护一个计数器，计算 push() 和 pop() 操作的次数。 创建一个迭代器时，将此值存储为迭代器实例变量。 在每次调用 hasNext() 和 next() 之前，检查该值是否自构造迭代器以来已更改；如果已更改，则抛出异常。
   
5. 带优先级的表达式求值。 编写一个程序 EvaluateDeluxe.java，扩展 Evaluate.java 以处理未完全括号化的表达式，使用标准的运算符 +、-、* 和 / 的优先级顺序。
   

网络练习

1. 尾部。 编写一个程序 Tail，使得 Tail k < file.txt 打印文件 file.txt 的最后 k 行。使用 StdIn.readLine()。应该使用哪种数据结构？
   
2. 有界栈。 一个有界栈是一个最多容纳 N 个元素的栈。（应用：带有有限缓冲区的撤销或历史记录。）
   
3. 删除第 i 个元素。 创建一个支持以下操作的数据类型：isEmpty、insert 和 remove(int i)，其中删除操作删除并返回队列中最近添加的第 i 个对象。首先使用数组实现，然后使用链表实现。每个操作的运行时间是多少？
   
4. 动态缩小。 使用栈和队列的数组实现时，当数组不足以存储下一个元素时，我们会将数组大小加倍。如果我们执行了多次加倍操作，然后删除了很多元素，可能会得到一个比必要的大得多的数组。实现以下策略：每当数组的填充率低于 1/4 时，将其缩小到一半大小。解释为什么当填充率低于 1/2 时我们不将其缩小到一半大小。
   
5. 栈 + 最大值。 创建一个数据结构，有效支持栈操作（弹出和推入），并返回最大元素。假设元素是整数或实数，以便可以比较它们。
   提示：使用两个堆栈，一个用于存储所有元素，另一个用于存储最大值。
   
6. PostScript。 PostScript 是大多数打印机使用的基于堆栈的语言。使用一个堆栈实现 PostScript 的一个小子集。
   
7. 面试问题。 给定一个未知数量的字符串的堆栈，打印出倒数第 5 个字符串。在此过程中破坏堆栈是可以的。提示：使用一个包含 5 个元素的队列。
   
8. 标签系统。 编写一个程序，从命令行读取一个二进制字符串，并应用以下（00, 1101���标签系统：如果第一个位是 0，则删除前三位并追加 00；如果第一个位是 1，则删除前三位并追加 1101。只要字符串至少有 3 位，就重复此过程。尝试确定以下输入是否会停止或进入无限循环：10010, 100100100100100100。使用一个队列。
   
9. 图灵带。 实现一个一维图灵带。带由一系列单元格组成，每个单元格存储一个整数（初始化为 0）。在任何时刻，都有一个带头指向其中一个单元格。支持以下接口方法：moveLeft 将带头向左移动一个单元格，moveRight 将带头向右移动一个单元格，look 返回活动单元格的内容，write(int a) 将活动单元格的内容更改为 a。提示：使用一个 int 表示活动单元格，使用两个堆栈表示带的左侧和右侧部分。类似于文本编辑器缓冲区。
   
10. 回文检查器。 编写一个程序，读取一系列字符串并检查它们是否构成回文。忽略标点、空格和大小写。（A MAN, A PLAN, A CANAL - PANAMA）。使用一个栈和一个队列。
    
11. 流算法。 给定一长序列的项目，设计一个数据结构来存储最近看到的 k 个项目。
    
12. 2 M/M/1 队列。 下一个顾客被分配到两个队列中较小的一个。使用 2 个先进先出队列。当接近收费站时，总是选择较长的队列（或错误的车道）的感觉。假设两辆车同时进入收费站并选择相同长度的不同队列。计算一辆车领先另一辆车的平均时间长度。
    
13. M/M/k 队列。 比较 k 个独立的 M/M/1 队列和 M/M/k 队列。
    
14. M/G/1 队列。 分析具有不同服务分布（G = 一般）的排队模型。
    
15. 中缀表达式转后缀表达式并考虑优先级顺序。编写一个程序将中缀表达式转换为后缀表达式。从左到右扫描中缀表达式。

• 操作数：输出它。
  
• 左括号：推入栈中。
  
• 右括号：重复弹出栈中的元素并输出，直到遇到左括号。丢弃两个括号。
  
• 优先级高于栈顶的运算符：推入栈中。
  
• 优先级低于或等于栈顶的运算符：重复弹出栈中的元素并输出，直到栈顶的运算符具有更高的优先级。将扫描到的运算符推入栈中。之后，弹出栈中的剩余元素并输出。
  

16. 检查重复。 编写一个代码片段，确定一个袋子是否包含任何重复项目。使用两个嵌套迭代器。
    
17. 检查三重复。 编写一个代码片段，确定一个袋子是否包含至少三次重复的项目。使用三重嵌套迭代器。
    
18. 相等。 如果两个队列按相同顺序包含相同项目，则它们相等。如果两个袋子包含相同项目但顺序不同，则它们相等。
    
19. 整数集合。 创建一个表示 0 到 N-1 之间（无重复）整数集合的数据类型。支持add(i)，exists(i)，remove(i)，size()，intersect，difference，symmetricDifference，union，isSubset，isSuperSet和isDisjointFrom。包括一个迭代器。
    
20. 冒号。 有经验的程序员知道，像下面这样写一个循环通常是一个坏主意

for (double x = 0.0; x <= N; x += 0.1) {
   ..
}

1. 由于浮点精度的结果，如果 N = xxx，则循环将执行 10N 次，如果 N = yyy，则执行 10N + 1 次。创建一个数据类型Mesh，使得x从left到right以delta的大小增量。假设right >= left，则循环应该恰好执行1 + floor((right - left) / delta)次。

for (double x : new Mesh(left, right, delta)) {
   ..
}

1. 这是 MATLAB 中冒号运算符的工作原理。您还应该对程序进行调试，以确保即使left > right且delta为负数也能正常工作。
2. 列表迭代器。 我们可能还想包括用于在列表中向后移动的方法hasPrevious()和previous()。要实现previous()，我们可以使用双向链表。程序 DoublyLinkedList.java 实现了这种策略。它使用 Java 的java.util.ListIterator接口支持向前和向后移动。我们实现了所有可选方法，包括remove()，set()和add()。remove()方法删除next()或previous()返回的最后一个元素。set()方法覆盖next()或previous()返回的最后一个元素的值。add()方法在next()将返回的下一个元素之前插入一个元素。只有在调用next()或previous()之后，且没有调用remove()或add()之后，才能调用set()和remove()是合法的。
   我们使用一个虚拟的头节点和尾节点来避免额外的情况。我们还存储一个额外的变量lastAccessed，它存储在最近一次调用next()或previous()时访问的节点。删除元素后，我们将lastAccessed重置为null；这表示调用remove()是非法的（直到随后调用next()或previous()为止）。
   
3. 双向迭代器。 定义一个支持四种方法的接口TwoWayIterator：hasNext()，hasPrevious()，next()和previous()。实现一个支持TwoWayIterator的列表。提示：使用数组或双向链表实现列表。
   
4. 将一个袋子添加到另一个末尾。 编写一个方法，将一个袋子 b 的项目添加到调用方的末尾。假设两个袋子存储相同类型的项目。
   提示：使用迭代器遍历 b 的项目，并将每个项目添加到调用方的末尾。
   
5. 替换所有。 编写一个方法，在队列或栈中用项目from替换所有出现的项目to。
   
6. 将列表添加到自身。 以下代码片段的结果是什么？

List list1 = new ArrayList();
List list2 = new ArrayList();
list1.add(list2);
list2.add(list1);
System.out.println(list1.equals(list2));
List list = new ArrayList();
list.add(list);
System.out.println(list.hashCode());

1. 答案： 栈溢出。Java 文档中说：“虽然列表可以包含自身作为元素，但极度谨慎是明智的：在这样的列表上，equals 和 hashCode 方法不再被很好地定义。”
2. 歌曲播放列表。 创建一个支持以下操作的数据类型：enqueue（将新歌曲添加到列表末尾）、play（打印下一首歌曲的名称）、skip（跳过列表中的下一首歌曲，不打印其名称）和back（返回上一首歌曲）。使用支持前向和后向迭代器的列表。
   
3. Josephus。 程序 Josephus.java 计算 Josephus 数。
   
4. 以下代码会按升序打印出整数 0 到 9 吗？

int[] vals = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int val : vals) {
   System.out.print(val + " ");
   StdRandom.shuffle(vals);     // mutate the array while iterating
}
System.out.println();

1. 不会。它会打印出 10 个值，但会有一些重复项，并且不会按升序排列。迭代器不会保存原始数组的副本 - 相反，它使用已变异的副本。
2. 使用一个访问指针实现队列。 重新实现一个队列，所有操作都需要恒定时间，但只有一个实例变量（而不是两个）。提示： 使用循环链表，保持指向最后一个项目的指针。
   
3. Steque。 栈结束队列或steque是一种支持 push、pop 和 enqueue 的数据类型。Knuth 将其称为输出受限双端队列。使用单链表实现它。
   
4. 使用两个栈实现队列。 实现一个使用两个栈的队列，使得每个队列操作都需要恒定的摊销栈操作次数。提示： 如果你将元素推入栈然后全部弹出，它们会以相反顺序出现。如果你重复这个过程，它们现在又会按顺序排列。
   *解决方案：*QueueWithTwoStacks.java。
   
5. 使用恒定数量的栈实现队列。 实现一个使用恒定数量的栈的队列，使得每个队列操作都需要恒定（最坏情况）的栈操作次数。警告： 难度非常高。
   
6. 使用队列实现栈。 实现一个使用单个队列的栈，使得每个栈操作都需要线性数量的队列操作。提示： 要删除一个项目，逐个获取队列中的所有元素，并将它们放在末尾，除了最后一个应该删除并返回。（诚然非常低效。）
   
7. 使用 Deque 实现两个栈。 使用单个 Deque 实现两个栈，使得每个操作都需要恒定数量的 Deque 操作。
   
8. 使用两个栈实现 Steque。（R. Tarjan） 实现一个使用两个栈的 Steque，使得每个 Steque 操作都需要恒定的摊销栈操作次数。
   
9. 使用栈和 Steque 实现 Deque。（R. Tarjan） 实现一个使用栈和 Steque 的 Deque，使得每个 Deque 操作都需要恒定的摊销栈和 Steque 操作次数。
   
10. 使用三个栈实现 Deque。（R. Tarjan） 实现一个使用三个栈的 Deque，使得每个 Deque 操作都需要恒定的摊销栈操作次数。
    
11. 多词搜索。 程序 MultiwordSearch.java 从命令行读取查询词 q[1]，…，q[k]的序列，从标准输入读取文档单词 d[1]，…，d[N]的序列，并找到这些 k 个单词按相同顺序出现的最短间隔。（这里最短意味着间隔中的单词数。）即找到索引 i 和 j，使得 d[i1] = q[1]，d[i2] = q[2]，…，d[ik] = q[k]，且 i1 < i2 < … < ik。
    答案：对于每个查询词，创建一个在文档中出现的索引的排序列表。按照 2 到 k 的顺序扫描列表，删除每个列表前面的索引，直到生成的 k 个列表的第一个元素按升序排列。

q[1]: 50 123 555 1002 1066
q[2]: 33 44 93 333 606 613
q[3]: 60 200
q[4]: 12 18 44 55 203 495
q[1]: 50 123 555 1002 1066
q[2]: 93 333 606 613
q[3]: 200
q[4]: 203 495

1. 列表 1 上的第一个元素序列形成包含列表 1 上第一个元素的最短间隔。
   现在删除列表 1 上的第一个元素。重复删除列表 2 中的元素，直到它与列表 1 一致。对列表 3 重复此操作，直到整个数组按升序排列。检查这个序列的第一个元素等等。
2. M/M/1 队列.马尔可夫/马尔可夫/单服务器模型是运筹学和概率论中的基本排队模型。任务以特定速率 λ 按泊松过程到达。这意味着每小时到达 λ 个顾客。���具体地说，到达遵循均值为 1 / λ 的指数分布：在时间 0 和 t 之间到达 k 个的概率是 (λ t)^k e^(-λ t) / k!。任务按照率为 μ 的泊松过程按 FIFO 顺序服务。两个 M 代表马尔可夫：这意味着系统是无记忆的：到达之间的时间是独立的，离开之间的时间也是独立的。M/M/1 模型分析。我们感兴趣的是理解排队系统。如果 λ > μ，则队列大小会无限增加。对于像 M/M/1 这样的简单模型，我们可以使用概率论来分析这些数量。假设 μ > λ，系统中恰好有 n 个顾客的概率是 (λ / μ)^n (1 - λ / μ)。

• L = 系统中平均顾客数量 = λ / (μ - λ).
  
• L[Q] = 队列中平均顾客数量 = λ² / (μ (μ - λ)).
  
• W = 顾客在系统中的平均时间 = 1 / (μ - λ).
  
• W[Q] = 顾客在队列中的平均时间 = W - 1 / μ.
  

3. 程序 MM1Queue.java 对于更复杂的模型，我们需要使用这样的模拟。变体：多个队列，多个服务器，顺序多级服务器，使用有限队列并测量被拒绝的顾客数量。应用：麦当劳的顾客，互联网路由器中的数据包，
   
4. 列出文件. Unix 目录是文件和目录的列表。程序 Directory.java 接受目录名称作为命令行参数，并按级别顺序打印出该目录中包含的所有文件（以及任何子目录）。它使用一个队列。
   
5. 中断处理. 当编写可以被中断的实时系统（例如，通过鼠标点击或无线连接）时，有必要立即处理中断，然后再继续当前活动。如果中断应按照到达顺序处理，则 FIFO 队列是适当的数据结构。
   
6. 库实现. Java 有一个名为 Stack 的内置库，但您应该避免使用它。它具有不通常与堆栈相关联的附加操作，例如获取第 i 个元素和将元素添加到堆栈底部（而不是顶部）。尽管具有这些额外操作可能看起来是一个奖励，但实际上是一个诅咒。我们使用 ADT 不是因为它们提供了每个可用的操作，而是因为它们限制了我们可以执行的操作类型！这可以防止我们执行我们实际上不想要的操作。如果我们需要的不仅仅是 LIFO 访问，我们应该使用不同的数据类型。我们仍然可以从 Java 库构建一个堆栈数据类型，但我们要小心限制操作类型。没有 Java 队列实现。
   
7. 负载平衡. N 个用户必须在网络中的 N 个相同服务器中进行选择。目标：平衡用户在资源之间的分布。检查每个资源以找到一个空闲的（或最不忙的）资源太昂贵了。相反，选择一个随机服务器。在任何步骤中，您应该能够看到每台机器上的作业。程序 Server.java 绘制负载分布。理论：平均负载 = 1，最大负载 = log N / log log N。
   
8. 负载平衡再加载. (Azar, Broder, Karlin, and Upfal) 选择两个随机资源。插入到两者中最不忙的资源上。理论：平均负载 = 1，最大负载 = log log N。
   
9. *网格化。*给定单位盒中的 N 个欧几里得点和参数 d，找到所有距离 d 以内的点对。将盒子分成一个 G×G 的网格，其中 G = ceil(1/d)。将所有点放入给定网格单元格中的列表。任何距离 d 以内的邻居必须在该单元格或其 8 个邻居之一中。程序 Grid.java 使用辅助数据类型 Point2D.java 实现了这种策略。
   
10. *Java 库。*Java 包含库类LinkedList和ArrayList，实现了一个列表。比我们的Sequence数据类型具有更广泛的接口：通过索引访问元素，删除元素，搜索元素。没有 urns。
    
11. 为Stack添加一个名为dup()的方法，用于创建顶部元素的副本并将其推入栈中。
    
12. 为Stack添加一个名为exch()的方法，用于交换栈顶部的两个元素。
    
13. 为Stack添加一个名为size()的方法，返回栈中的元素数量。
    
14. 为Stack添加一个名为Item[] multiPop(int k)的方法，从栈中弹出 k 个元素并将它们作为对象数组返回。
    
15. 为Queue添加一个名为Item[] toArray()的方法，将队列中的所有 N 个元素作为长度为 N 的数组返回。
    
16. 编写一个递归函数，该函数以队列作为输入，并重新排列队列，使其顺序相反。提示：出队第一个元素，递归反转队列，然后入队第一个元素。
    
17. 给定一个队列，创建两个新队列 q1 和 q2，使得 q1 包含 q 的偶数元素，q2 包含奇数元素，例如，就像处理一副牌一样。
    
18. 以下代码片段做什么？

Queue<Integer> q = new Queue<Integer>();
q.enqueue(0);
q.enqueue(1);
for (int i = 0; i < 10; i++) {
    int a = q.dequeue();
    int b = q.dequeue();
    q.enqueue(b);
    q.enqueue(a + b);
    System.out.println(a);
}

1. 在文字处理器中实现“撤销”功能，您会选择哪种数据类型来实现？
   
2. 假设您有一个大小为 N 的单个数组，并且希望实现两个栈，以便在两个栈上的元素总数为 N+1 之前不会溢出。您将如何实现这一点？
   
3. 假设您在 Stack.java 的链表实现中使用以下代码实现push。错误在哪里？

public void push(Item item) {
   Node second = first;
   Node first = new Node();
   first.item = item;
   first.next = second;
}

1. 答案：通过重新声明first，您创建了一个名为first的新局部变量，它与名为first的实例变量不同。
2. **最小栈。**设计一个数据类型，实现以下操作，所有操作都在常数时间内完成：推送，弹出，最小值。假设项目是Comparable的。
   解决方案：维护两个栈，一个包含所有项目，另一个包含最小值。要推送项目，请将其推送到第一个栈；如果它小于第二个栈的顶部项目，请将其也推送到第二个栈。要弹出项目，请从第一个栈弹出；如果它是第二个栈的顶部项目，请也从第二个栈弹出。要找到最小值，请返回第二个栈的顶部项目。
   
3. **翻倍和减半。**将 ResizingArrayStack.java 中的减半测试从if (N > 0 && N == a.length/4) resize(a.length/2);替换为if (N == a.length/4) resize(2*N);的效果是什么？
   
4. **Shunting-yard 算法。**实现 Dijkstra 的shunting-yard 算法将中缀表达式转换为后缀表达式。支持运算符优先级，包括左结合和右结合运算符。
   
5. **FIFO 队列与随机删除。**实现一个数据类型，支持插入一个项目，删除最近添加的项目和删除一个随机项目。每个操作应该在每次操作中花费常数期望摊销时间，并且应该使用空间（最多）与数据结构中的项目数量成比例。
   
6. **股票价格。**给定每日股票价格数组prices[]，创建一个数组days[]，使得days[i]告诉您从第i天开始，直到股票价格超过prices[i]需要等待多少天。
   提示：你的算法应该以线性时间运行，并使用一个数组索引的栈。
   

1.4 算法分析

原文：algs4.cs.princeton.edu/14analysis

译者：飞龙

协议：CC BY-NC-SA 4.0

随着人们在使用计算机方面的经验增加，他们用计算机来解决困难问题或处理大量数据，不可避免地会引发这样的问题：

• 我的程序需要多长时间？
  
• 为什么我的程序会耗尽内存？
  

科学方法。

科学家用来理解自然界的方法同样适用于研究程序的运行时间：

• 观察自然界的某些特征，通常是通过精确的测量。
  
• 假设 一个与观察一致的模型。
  
• 使用假设预测事件。
  
• 通过进一步观察验证预测。
  
• 通过重复直到假设和观察一致来验证。
  

我们设计的实验必须是可重复的，我们制定的假设必须是可证伪的。

观察。

我们的第一个挑战是确定如何对程序的运行时间进行定量测量。Stopwatch.java 是一种测量程序运行时间的数据类型。

ThreeSum.java 计算一个包含 N 个整数的文件中总和为 0 的三元组的数量（忽略整数溢出）。DoublingTest.java 生成一系列随机输入数组，每一步将数组大小加倍，并打印 ThreeSum.count() 的运行时间。DoublingRatio.java 类似，但还输出从一个大小到下一个大小的运行时间比率。

数学模型。

一个程序的总运行时间由两个主要因素决定：执��每个语句的成本和每个语句的执行频率。

• 波浪线近似。 我们使用波浪线近似，其中我们丢弃复杂化公式的低阶项。我们写 ~ f(N) 来表示任何函数，当除以 f(N) 时，随着 N 的增长趋近于 1。我们写 g(N) ~ f(N) 来表示当 N 增长时，g(N) / f(N) 趋近于 1。
• 
  
• 增长顺序分类。 我们通常使用形式为 g(N) ~ a f(N) 的波浪线近似，其中 f(N) = N^b log^c N，并将 f(N) 称为 g(N) 的增长顺序。我们只使用几个结构原语（语句、条件、循环、嵌套和方法调用）来实现算法，因此成本的增长顺序往往是问题大小 N 的几个函数之一。
  
• 成本模型。 我们通过阐明定义基本操作的成本模型来关注算法的属性。例如，对于 3-sum 问题，一个适当的成本模型是我们访问数组条目的次数，无论是读取还是写入。
  

性质。 ThreeSum.java 的运行时间增长顺序为 N³。

命题。 暴力 3-sum 算法使用*~ N³ / 2* 数组访问来计算在 N 个数字中总和为 0 的三元组的数量。

设计更快的算法。

研究程序增长顺序的一个主要原因是帮助设计更快的算法来解决相同的问题。使用归并排序和二分查找，我们为 2-sum 和 3-sum 问题开发了更快的算法。

• 2-sum. 暴力解决方案 TwoSum.java 需要的时间与 N² 成正比。TwoSumFast.java 在时间上与 N log N 成正比地解决了 2-sum 问题。
  
• 3-sum. ThreeSumFast.java 在时间上与 N² log N 成正比地解决了 3-sum 问题。
  

处理对输入的依赖。

对于许多问题，运行时间可能会根据输入而有很大的变化。

• 输入模型. 我们可以仔细地对要处理的输入类型进行建模。这种方法具有挑战性，因为模型可能是不现实的。
  
• 最坏情况性能保证. 程序的运行时间小于某个界限（作为输入大小的函数），无论输入是什么。这种保守的方法可能适用于运行核反应堆、心脏起搏器或汽车刹车的软件。
  
• 随机算法. 提供性能保证的一种方法是引入随机性，例如快速排序和哈希。每次运行算法时，它都会花费不同的时间。这些保证并不是绝对的，但它们无效的几率小于你的计算机被闪电击中的几率。因此，这些保证在实践中与最坏情况的保证一样有用。
  
• 摊销分析. 对于许多应用程序，算法的输入可能不仅仅是数据，还包括客户端执行的操作序列。摊销分析提供了对操作序列的最坏情况性能保证。
  

命题. 在Bag、Stack和Queue的链表实现中，所有操作在最坏情况下都需要常数时间。

命题. 在Bag、Stack和Queue的调整大小数组实现中，从空数据结构开始，任何长度为N的操作序列在最坏情况下需要与N成比例的时间（摊销每个操作的常数时间）。

内存使用。

要估算我们的程序使用了多少内存，我们可以计算变量的数量，并根据它们的类型按字节加权。对于典型的 64 位机器，

• 原始类型. 下表给出了原始类型的内存需求。
• 
  
• 对象. 要确定对象的内存使用量，我们将每个实例变量使用的内存量加到与每个对象相关联的开销上，通常为 16 字节。此外，内存使用量通常会填充为 8 字节的倍数（在 64 位机器上）。
• 
  
• 参考文献. 对象的引用通常是一个内存地址，因此在 64 位机器上使用 8 字节的内存。
  
• 链表. 嵌套的非静态（内部）类，比如我们的Node类，需要额外的 8 字节开销（用于引用封闭实例）。
  
• 数组. Java 中的数组被实现为对象，通常需要额外的开销来存储长度。原始类型值的数组通常需要 24 字节的头信息（16 字节的对象开销，4 字节的长度，和 4 字节的填充），再加上存储值所需的内存。
• 
  
• 字符串. Java 7 中长度为N的字符串通常使用 32 字节（用于String对象），再加上 24 + 2N字节（用于包含字符的数组），总共为 56 + 2N字节。
  

根据上下文，我们可能会或不会递归地计算对象的内存引用。例如，我们会计算String对象中的char[]数组的内存，因为这段内存是在创建字符串时分配的。但是，我们通常不会计算StackOfStrings对象中String对象的内存，因为这些String对象是由客户端创建的。

问与答

问. 如何增加 Java 分配的内存和堆栈空间？

A. 你可以通过使用 java -Xmx200m Hello 来增加分配给 Java 的内存量，其中 200m 表示 200 兆字节。默认设置通常为 64MB。你可以通过使用 java -Xss200k Hello 来增加分配给 Java 的堆栈空间量，其中 200k 表示 200 千字节。默认设置通常为 128KB。你可以通过使用 java -Xmx200m -Xss200k Hello 来同时增加内存和堆栈空间的量。

Q. 填充的目的是什么？

A. 填充使所有对象占用的空间是 8 字节的倍数。这可能会浪费一些内存，但可以加快内存访问和垃圾回收速度。

Q. 我在我的计算实验中得到了不一致的时间信息。有什么建议吗？

A. 确保你的计算消耗足够的 CPU 周期，以便你可以准确地测量它。通常，1 秒到 1 分钟是合理的。如果你使用了大量内存，那可能是瓶颈。考虑关闭 HotSpot 编译器，使用 java -Xint，以确保更统一的测试环境。缺点是你不再准确地测量你想要测量的内容，即实际运行时间。

Q. 如果考虑垃圾回收和其他运行时进程，链表实现的栈或队列是否真的保证每次操作的常数时间？

A. 我们的分析没有考虑许多系统效应（如缓存、垃圾回收和即时编译）-在实践中，这些效应很重要。特别是，默认的 Java 垃圾收集器仅保证每次操作的摊销常数时间。然而，有实时垃圾收集器保证最坏情况下每次操作的常数时间。实时 Java提供了 Java 的扩展，为各种运行时进程（如垃圾回收、类加载、即时编译和线程调度）提供最坏情况下的性能保证。

练习

1. 给出以下代码片段的运行时间的增长顺序（作为N的函数）：

int sum = 0;
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++) 
      sum++;

int sum = 0;
for (int i = 1; i < N; i *= 2)
   for(int j = 0; j < i; j++)
      sum++;

int sum = 0;
for (int i = 1; i < N; i *= 2)
   for (int j = 0; j < N; j++)
      sum++;

1. 答案：线性（N + N/2 + N/4 + …）；线性（1 + 2 + 4 + 8 + …）；线性对数级（外部循环循环 lg N 次）。

创意问题

1. 4-求和。 对 FourSum.java 问题开发一个蛮力解决方案。
   
2. 数组中的局部最小值。 编写一个程序，给定一个由 n 个不同整数组成的数组 a[]，找到一个局部最小值：一个索引 i，使得a[i] < a[i-1] 和 a[i] < a[i+1]（假设相邻条目在范围内）。在最坏情况下，你的程序应该使用 ~ 2 lg n 次比较。
   答案：检查中间值 a[n/2] 及其两个邻居 a[n/2 - 1] 和 a[n/2 + 1]。如果 a[n/2] 是局部最小值，则停止；否则在较小邻居的一半中搜索。
   
3. 矩阵中的局部最小值。 给定一个由 n² 个不同整数组成的 n×n 数组 a[]，设计一个算法，其运行时间与 n log n 成正比，以找到一个局部最小值：一对索引 i 和 j，使得 a[i][j] < a[i+1][j]，a[i][j] < a[i][j+1]，a[i][j] < a[i-1][j]，以及 a[i][j] < a[i][j-1]（假设相邻条目在范围内）。
   提示：找到第 n/2 行中的最小条目，称为 a[n/2][j]。如果它是局部最小值，则返回它。否则，检查它的两个垂直邻居 a[n/2-1][j] 和 a[n/2+1][j]。在较小邻居的一半中进行递归。
   额外奖励：设计一个算法，其运行时间与 n 成正比。
   
4. 双峰搜索。 如果一个数组由一个递增的整数序列紧接着一个递减的整数序列组成，则该数组是双峰的。编写一个程序，给定一个由 n 个不同 int 值组成的双峰数组，确定给定的整数是否在数组中。在最坏情况下，你的程序应该使用 ~ 3 log n 次比较。
   答案: 使用二分查找的一个版本，如 BitonicMax.java 中所示，找到最大值（在~ 1 lg n次比较中）；然后使用二分查找在每个片段中搜索（每个片段在~ 1 lg n次比较中）。
   
5. 只使用加法和减法的二分查找。 [Mihai Patrascu] 编写一个程序，给定一个按升序排列的包含n个不同整数的数组，确定给定的整数是否在数组中。你只能使用加法和减法以及恒定数量的额外内存。你的程序在最坏情况下的运行时间应与 log n成比例。
   答案: 不要基于二的幂（二分查找）进行搜索，而是使用斐波那契数（也呈指数增长）。保持当前搜索范围为[i, i + F(k)]，并将 F(k)、F(k-1)保存在两个变量中。在每一步中，通过减法计算 F(k-2)，检查元素 i + F(k-2)，并将范围更新为[i, i + F(k-2)]或[i + F(k-2), i + F(k-2) + F(k-1)]。
   
6. 带有重复项的二分查找。 修改二分查找，使其始终返回与搜索键匹配的项的键的最小（最大）索引。
   
7. 从建筑物上扔鸡蛋。 假设你有一座N层的建筑物和大量的鸡蛋。假设如果鸡蛋从第F层或更高处扔下，就会摔碎，否则不会。首先，设计一种策略来确定F的值，使得在使用*~ lg N次扔鸡蛋时破碎的鸡蛋数量为~ lg N*，然后找到一种方法将成本降低到*~ 2 lg F*，当N远大于F时。
   提示: 二分查找；重复加倍和二分查找。
   
8. 从建筑物上扔两个鸡蛋。 考虑前面的问题，但现在假设你只有两个鸡蛋，你的成本模型是扔鸡蛋的次数。设计一种策略，确定F，使得扔鸡蛋的次数最多为 2 sqrt(√ N)，然后找到一种方法将成本降低到*~c √ F*，其中 c 是一个常数。
   第一部分的解决方案: 为了达到 2 * sqrt(N)，在 sqrt(N)、2 * sqrt(N)、3 * sqrt(N)、…、sqrt(N) * sqrt(N)层放置鸡蛋。（为简单起见，我们假设 sqrt(N)是一个整数。）假设鸡蛋在第 k * sqrt(N)层摔碎。用第二个鸡蛋，你应该在区间(k-1) * sqrt(N)到 k * sqrt(N)中进行线性搜索。总共，你最多需要进行 2 * sqrt(N)次试验就能找到楼层 F。
   第二部分的提示: 1 + 2 + 3 + … k ~ 1/2 k²。
   
9. 热还是冷。 你的目标是猜测一个介于 1 和N之间的秘密整数。你反复猜测介于 1 和N之间的整数。每次猜测后，你会得知它是否等于秘密整数（游戏停止）；否则（从第二次猜测开始），你会得知猜测是更热（更接近）还是更冷（距离更远）比你之前的猜测。设计一个算法，在*~ 2 lg N次猜测中找到秘密数字。然后，设计一个算法，在~ 1 lg N*次猜测中找到秘密数字。
   提示: 第一部分使用二分查找。对于第二部分，首先设计一个算法，在*~1 lg N次猜测中解决问题，假设你被允许在范围-N到 2N*中猜测整数。
   

网页练习

1. 设 f 是一个单调递增的函数，满足 f(0) < 0 且 f(N) > 0。找到最小的整数 i，使得 f(i) > 0。设计一个算法，使得对 f()的调用次数为 O(log N)。
   
2. 上下取整。 给定一组可比较的元素，x 的上取整是集合中大于或等于 x 的最小元素，下取整是小于或等于 x 的最大元素。假设你有一个按升序排列的包含 N 个项的数组。给出一个 O(log N)的算法，找到 x 的上取整和下取整。
   
3. 使用 lg N 两路比较进行排名。 实现rank()，使其使用~ 1 lg N 两路比较（而不是~ 1 lg N 三路比较）。
   
4. 身份。 给定一个按升序排列的包含 N 个不同整数（正数或负数）的数组 a。设计一个算法来找到一个索引 i，使得 a[i] = i，如果这样的索引存在的话。提示：二分查找。
   
5. 多数派。 给定一个包含 N 个字符串的数组。如果一个元素出现次数超过 N/2 次，则称其为多数派。设计一个算法来识别多数派是否存在。你的算法应在线性对数时间内运行。
   
6. 多数派。 重复上一个练习，但这次你的算法应在线性时间内运���，并且只使用恒定数量的额外空间。此外，你只能比较元素是否相等，而不能比较字典顺序。
   答案：如果 a 和 b 是两个元素且 a != b，则移除它们两个；多数派仍然存在。使用 N-1 次比较找到多数派的候选者；使用 N-1 次比较检查候选者是否真的是多数派。
   
7. 第二小元素。 给出一个算法，使用最少的比较次数从 N 个项目的列表中找到最小和第二小的元素。答案：通过构建一个锦标赛树，在 ceil(N + lg(N) - 2) 次比较中完成。每个父节点都是其两个子节点中的最小值。最小值最终在根节点处；第二小值在根节点到最小值的路径上。
   
8. 查找重复项。 给定一个包含 N 个元素的数组，其中每个元素是介于 1 和 N 之间的整数，请编写一个算法来确定是否存在任何重复项。你的算法应在线性时间内运行，并使用 O(1) 额外空间。提示：你可以破坏数组。
   
9. 查找重复项。 给定一个包含 N+1 个元素的数组，其中每个元素是介于 1 和 N 之间的整数，请编写一个算法来查找重复项。你的算法应在线性时间内运行，使用 O(1) 额外空间，并且不得修改原始数组。提示：指针加倍。
   
10. 查找共同元素。 给定两个包含 N 个 64 位整数的数组，设计一个算法来打印出两个列表中都出现的所有元素。输出应按排序顺序排列。你的算法应在 N log N 时间内运行。提示：归并排序，归并排序，合并。备注：在基于比较的模型中，不可能比 N log N 更好。
    
11. 查找共同元素。 重复上述练习，但假设第一个数组有 M 个整数，第二个数组有 N 个整数，其中 M 远小于 N。给出一个在 N log M 时间内运行的算法。提示：排序和二分查找。
    
12. 变位词。 设计一个 O(N log N) 算法来读取一个单词列表，并打印出所有的变位词。例如，字符串 “comedian” 和 “demoniac” 是彼此的变位词。假设有 N 个单词，每个单词最多包含 20 个字母。设计一个 O(N²) 的算法应该不难，但将其降至 O(N log N) 需要一些巧妙的方法。
    
13. 在排序、旋转数组中搜索。 给定一个包含 n 个不同整数的排序数组，该数组已经旋转了未知数量的位置，例如，15 36 1 7 12 13 14，请编写一个程序 RotatedSortedArray.java 来确定给定的整数是否在列表中。你的算法的运行时间增长应为对数级别。
    
14. 找到数组中的跳跃。 给定一个由 n 个整数组成的数组，形式为 1, 2, 3, …, k-1, k+j, k+j+1, …, n+j，其中 1 <= k <= n 且 j > 0，请设计一个对数时间算法来找到整数 k。也就是说，数组包含整数 1 到 n，只是在某个点上，所有剩余值都增加了 j。
    
15. 找到缺失的整数。 一个数组 a[] 包含从 0 到 N 的所有整数，除了 1。但是，你不能通过单个操作访问一个元素。相反，你可以调用 get(i, k)，它返回 a[i] 的第 k 位，或者你可以调用 swap(i, j)，它交换 a[] 的第 i 和第 j 个元素。设计一个 O(N) 算法来找到缺失的整数。为简单起见，假设 N 是 2 的幂。
    
16. 最长的 0 行。 给定一个由 0 和 1 组成的 N×N 矩阵，使得在每行中 0 不会出现在 1 之前，找到具有最多 0 的行，并在 O(N) 时间内完成。
    
17. 单调二维数组。 给定一个 n×n 的元素数组，使得每行按升序排列，每列也按升序排列，设计一个 O(n)的算法来确定数组中是否存在给定元素 x。你可以假设 n×n 数组中的所有元素都是不同的。
    
18. 你站在一条路中间，但有一场尘暴遮挡了你的视线和方向。只有一个方向有庇护所，但直到你站在它面前才能看到任何东西。设计一个能够找到庇护所的算法，保证能找到。你的目标是尽量减少步行的距离。提示：某种来回走动的策略。
    
19. 通过尽可能大的常数因子改进以下代码片段，以适应大规模 n。通过性能分析确定瓶颈在哪里。假设b[]是一个长度为n的整数数组。

double[] a = new double[n];
for (int i = 0; i < n; i++)
   for (int j = 0; j < n; j++)
       a[j] += Math.exp(-0.5 * (Math.pow(b[i] - b[j], 2)); 

1. 原地置换。 编写一个程序Permutation.java，其中包含接受数组和置换（或逆置换）的函数，并根据置换（或逆置换）重新排列数组中的元素。原地操作：只使用恒定量的额外内存。
   
2. 三数之和。 给定三个集合 A、B 和 C，每个集合最多包含 N 个整数，确定是否存在三元组 a 在 A 中，b 在 B 中，c 在 C 中，使得 a + b + c = 0。
   答案：按升序对 B 进行排序；按降序对 C 进行排序；对于 A 中的每��a，扫描 B 和 C，找到一个对，使得它们的和为-a（当和太小时，在 B 中前进，当和太大时，在 C 中前进）。
   
3. 两数之和。 给定两个集合 A 和 B，每个集合最多包含 N 个整数，确定 A 中任意两个不同整数的和是否等于 B 中的一个整数。
   
4. 连续和。 给定一组实数和目标值 V，找到一个连续块（任意长度），其和尽可能接近 V。
   暴力法：通过暴力法计算每个连续块的总和。这需要 O(N³)的时间。
   部分和：计算所有部分和 s[i] = a[0] + a[1] + … + a[i]，以便连续块的和形式为 s[j] - s[i]。这需要 O(N²)的时间。
   排序和二分查找：按上述方式形成部分和，然后按升序对它们进行排序。对于每个 i，二分查找尽可能接近 s[i]的 s[j]。这需要 O(N log N)的时间。
   
5. 三变量的线性方程。 对于三个变量的固定线性方程（例如整数系数），给定 N 个数字，其中任意三个是否满足方程？为该问题设计一个二次算法。提示：参见三数之和的二次算法。
   
6. 卷积三数之和。 给定 N 个实数，确定是否存在索引 i 和 j，使得 a[i] + a[j] = a[i+j]。为该问题设计一个二次算法。提示：参见三数之和的二次算法。
   
7. 找到主要项。 给定一个从标准输入中任意长的项序列，其中一个项出现的次数严格占多数，识别主要项。只使用恒定量的内存。
   解决方案。 维护一个整数计数器和一个变量来存储当前的冠军项。读取下一个项，如果该项等于冠军项，则将计数器加一。(ii) 否则将计数器减一，如果计数器达到 0，则用当前项替换冠军值。终止时，冠军值将是主要项。
   
8. 数组的记忆。 MemoryOfArrays.java。依赖于 LinearRegression.java。
   
9. 字符串和子字符串的记忆。 MemoryOfStrings.java。依赖于 LinearRegression.java 和 PolynomialRegression.java。取决于你使用的是 Java 6 还是 Java 7。
   
10. 栈和队列的记忆。 作为 N 个项的栈的内存使用量是 N 的函数吗？
    解决方案。 32 + 40N（不包括引用对象的内存）。MemoryOfStacks.java。
    
11. 欧几里得算法的分析。 证明欧几里得算法的时间复杂度最多与N成正比，其中N是较大输入中的位数。
    答案：首先我们假设 p > q。如果不是，则第一个递归调用实际上会交换 p 和 q。现在，我们要证明在至多 2 次递归调用后，p 会减少一半。为了证明这一点，有两种情况需要考虑。如果 q ≤ p / 2，则下一个递归调用将有 p’ = q ≤ p / 2，因此在仅一次递归调用后，p 至少减少了一半。否则，如果 p / 2 < q < p，则 q’ = p % q = p - q < p / 2，因此 p’’ = q’ < p / 2，经过两次迭代后，p 将减少一半或更多。因此，如果 p 有 N 位，则在至多 2N 次递归调用后，欧几里得算法将达到基本情况。因此，总步数与 N 成正比。
    
12. 查找重复项。 给定一个包含 0 到 N 之间的 N+2 个整数的排序数组，其中恰好有一个重复项，设计一个对数时间复杂度的算法来找到重复项。
    提示 二分查找。
    
13. 给定一个包含 n 个实数的数组a[]，设计一个线性时间算法来找到a[j] - a[i]的最大值，其中j ≥ i。
    解决方案：

double best = 0.0;
double min = a[0];
for (int i = 0; i < n; i++) {
    min  = Math.min(a[i], min);
    best = Math.max(a[i] - min, best);
}

1. 给定一个包含 n 个实数的数组a[]，设计一个线性时间算法来找到|a[j] - a[i]| + |j - i|的最大值。
   提示：创建两个长度为 n 的数组 b[]和 c[]，其中 b[i] = a[i] - i，c[i] = a[i] + i。
   

1.5 案例研究：并查集

原文：algs4.cs.princeton.edu/15uf

译者：飞龙

协议：CC BY-NC-SA 4.0

动态连通性。

输入是一系列整数对，其中每个整数表示某种类型的对象，我们将解释对p q为p连接到q。我们假设“连接到”是一个等价关系：

• 对称性：如果p连接到q，那么q连接到p。
  
• 传递性：如果p连接到q且q连接到r，那么p连接到r。
  
• 自反性：p连接到p。
  

等价关系将对象划分为等价类或连通分量。

我们的目标是编写一个程序来过滤序列中的多余对：当程序从输入中读取一对p q时，只有当它到目前为止看到的对不意味着p连接到q时，它才将这对写入输出。如果之前的对确实意味着p连接到q，那么程序应忽略这对p q并继续读取下一对。

普林斯顿算法讲义（一）（4）https://developer.aliyun.com/article/1484170