CS61B 课程笔记（Lecture 26 Midterm 2 Review)

1. 复杂度分析

问题描述：

分析以下常见数据结构操作的时间复杂度，假设 (N) 是项的数量。主要分析的数据结构包括：

  1. 数组
  2. 链表
  3. 哈希表
  4. 平衡二叉搜索树（如 AVL 树、红黑树）

以下是各操作的时间复杂度分类：

数据结构操作：

1. 数组

  • .get 操作：
    • 最佳情况： (\(Θ(1)\)) — 直接通过索引访问目标元素。
    • 最坏情况： (\(Θ(1)\)) — 数组是随机访问的，不会影响时间复杂度。
  • .put 操作：
    • 最佳情况： (\(Θ(1)\)) — 在空位置直接插入元素。
    • 最坏情况： (\(Θ(N)\)) — 在数组满的情况下，可能需要扩展数组并复制元素。

2. 链表

  • .get 操作：
    • 最佳情况： (\(Θ(1)\)) — 当目标元素在头节点时。
    • 最坏情况： (\(Θ(N)\)) — 需要遍历整个链表找到目标元素。
  • .put 操作：
    • 最佳情况： (\(Θ(1)\)) — 在头节点插入元素。
    • 最坏情况： (\(Θ(1)\)) — 直接插入在尾部或在中间节点（若有尾指针）。

3. 哈希表

  • .get 操作：
    • 最佳情况： (\(Θ(1)\)) — 根据键直接访问值。
    • 最坏情况： (\(Θ(N)\)) — 当所有元素发生冲突并链入同一桶时。
  • .put 操作：
    • 最佳情况： (\(Θ(1)\)) — 直接插入到空位置。
    • 最坏情况： (\(Θ(N)\)) — 可能需要处理冲突，或者在最坏情况下重新哈希整个表。

4. 平衡二叉搜索树（如 AVL 树、红黑树）

  • .get 操作：
    • 最佳情况： (\(Θ(1)\)) — 直接找到根节点。
    • 最坏情况： (\(Θ(\log N)\)) — 树的高度为 (\(O(\log N)\))。
  • .put 操作：
    • 最佳情况： (\(Θ(1)\)) — 插入在空位置或简单情况。
    • 最坏情况： (\(Θ(\log N)\)) — 可能需要进行树的重平衡。

2. 优先级队列和堆

a) 优先级队列的 remove 方法：

问题描述：

设计一个有效的优先级队列的 remove 方法，使得最小值的访问时间为 (\(O(1)\))。假设优先级队列底层实现为最小堆。

解答：

1
2
3
4
5
6
7
8
public Comparable remove() {
  Comparable result = data.get(0); // 获取最小值
  // 交换 data[0] 和 data[data.size() - 1]
  data.set(0, data.get(data.size() - 1)); // 将最后一个元素放到根节点
  data.remove(data.size() - 1); // 移除最后一个元素
  heapifyDown(0); // 从根节点开始堆化
  return result;
}
  • 步骤解析：
    • 首先，获取最小值（根节点）并保存到 result 变量中。
    • 然后，将最后一个元素替换到根节点，以保持堆的结构。
    • 移除最后一个元素。
    • 通过调用 heapifyDown(0) 方法，从根节点开始调整堆，以确保最小堆性质得以恢复。

b) 时间复杂度比较：

问题描述：

比较上述 remove 方法的时间复杂度与使用 Collections.sort 的时间复杂度。

解答：

  • remove 方法的时间复杂度：
    • 获取最小值的时间为 (\(O(1)\))。
    • 交换根节点与最后一个元素的时间为 (\(O(1)\))。
    • 移除最后一个元素的时间为 (\(O(1)\))。
    • heapifyDown(0) 的时间复杂度为 (\(O(\log M)\))，其中 (\(M\)) 是当前堆中的元素数量。
    • 因此，remove 方法的总时间复杂度为 (\(O(\log M)\))。
  • Collections.sort 方法的时间复杂度：
    • 使用 Java 的 Collections.sort 方法，通常基于归并排序或快速排序，其时间复杂度为 (\(O(M \log M)\))。
  • 比较结果：
    • 因此，在处理优先级队列的最小值移除操作时，使用最小堆的 remove 方法在单次操作时的时间复杂度为 (\(O(\log M)\))，而使用 Collections.sort 方法的时间复杂度为 (\(O(M \log M)\))。
    • 在需要频繁进行删除操作的情况下，优先级队列的实现效率更高。

3. 图

b) 深度优先搜索（DFS）伪代码：

问题描述：

编写 DFS 算法的伪代码，并注释返回/重置条件。

解答：

1
2
3
4
5
DFS(node):
  if node is not visited:
    mark node as visited
    for each neighbor in node:
      DFS(neighbor)
  • DFS 的基本思想是从一个节点开始，访问它并标记为已访问，然后递归访问所有未访问的邻居节点。

c) 有向图边数计算：

问题描述：

计算一个包含 6 个顶点的有向图的边数，假设每个顶点与其他 5 个顶点相连（无自环）。

解答：

  • 边数 = (\(6 \times 5 = 30\))。

4. 广度优先搜索（BFS）

a) BFS 伪代码：

问题描述：

编写 BFS 算法的伪代码，并解释其过程。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
BFS(startNode):
  create a queue
  mark startNode as visited
  enqueue startNode

  while queue is not empty:
    currentNode = dequeue
    process(currentNode)
    for each neighbor of currentNode:
      if neighbor is not visited:
        mark neighbor as visited
        enqueue neighbor
  • BFS 从起始节点开始，将其标记为已访问并入队，然后重复从队列中出队节点，处理该节点并将其未访问的邻居入队，直到队列为空。

b) 处理已访问节点：

问题描述：

在图的 BFS 遍历中，如何处理已经访问过的节点？

解答：

  • 在实现过程中，需要在访问每个节点时进行标记，避免重复访问，确保每个节点只被处理一次。

c) 绘制 BFS 迭代状态：

问题描述：

在图中进行 BFS 时，绘制每次迭代后的状态（可视化过程）。

解答：

  • 可以绘制每一步入队和出队的节点，清楚展示 BFS 处理的顺序。

d) 添加边的影响：

问题描述：

如果在 BFS 的输入图中添加一条边，是否会影响算法的时间复杂度？请解释。

解答：

  • 添加边不会影响算法的时间复杂度，仍然为 (\(O(V + E)\))，其中 (\(V\)) 是顶点数，(\(E\)) 是边数。

5. 代码重构

问题描述：

重构以下代码段，以减少嵌套层次并提高可读性：

1
2
3
4
5
6
7
8
9
10
11
public void processValues(int a, int b) {
  if (a > b) {
    if (a > 10) {
      System.out.println(a + " is greater than 10");
    } else {
      System.out.println(a + " is not greater than 10");
    }
  } else {
    System.out.println(b + " is greater or equal to " + a);
  }
}

解答：

重构后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void processValues(int a, int b) {
  if (a > b) {
    processA(a);
  } else {
    System.out.println(b + " is greater or equal to " + a);
  }
}

private void processA(int a) {
  if (a > 10) {
    System.out.println(a + " is greater than 10");
  } else {
    System.out.println(a + " is not greater than 10");
  }
}
  • 在重构后的代码中，使用了一个辅助方法 processA 来处理 a 的情况，减少了嵌套层次，增强了代码的可读性。