CS61B 课程笔记（Disc 07 Asymptotic Analysis I)

CS 61B 渐进分析

1 渐进符号

1.1 大O运行时间排序

将以下大O运行时间从小到大排序：

  • $ O(1) $
  • \(O(\log n)\)
  • $O(n) $
  • $ O(n n)$
  • $O(n^2 n) $
  • \(O(n^3)\)
  • \(O(2^n)\)
  • $O(n!) $
  • $ O(n^n)$

排序结果： \(O(1) \subset O(\log n) \subset O(n) \subset O(n \log n) \subset O(n^2 \log n) \subset O(n^3) \subset O(2^n) \subset O(n!) \subset O(n^n)\)

2 渐进分析

2.1 分析运行时间

给出最坏情况和最好情况的运行时间（以 $M $ 和 \(N\) 为变量）。假设 ping 是 $ (1) $ 并返回一个整数。

1
2
3
4
5
6
7
8
int j = 0;
for (int i = N; i > 0; i--) {
    for (; j <= M; j++) {
        if (ping(i, j) > 64) {
            break;
        }
    }
}
  • 最坏情况: \(\Theta(M + N)\)
  • 最好情况: \(\Theta(N)\)
    说明: 关键在于 $ j$ 在循环外初始化！
2.2 分析运行时间

假设 \(N = \text{array.length}\) ，且 mrpoolsort(array) 是 \(\Theta(N \log N)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static boolean mystery(int[] array) {
    array = mrpoolsort(array);
    int N = array.length;
    for (int i = 0; i < N; i++) {
        boolean x = false;
        for (int j = 0; j < N; j++) {
            if (i != j && array[i] == array[j]) {
                x = true;
            }
        }
        if (!x) {
            return false;
        }
    }
    return true;
}
  • 最坏情况: $ (N^2) $
  • 最好情况: $ (N N) $
    记住: 开始的排序时间！

(a) mystery() 的作用是什么？
mystery() 返回数组中每个整数是否都有重复（例如：{1, 2, 1, 2} 为真，而 {1, 2, 2} 为假）。

(b) 使用 ADT 描述如何实现 mystery()，并假设每个整数在数组中最多出现两次，开发一个仅使用常量内存的解决方案。
使用 $(N) $ 的算法：使用一个映射，将元素作为键，出现次数作为值，确保所有值都大于 1。此方法使用 O(N) 的内存。
可以通过排序后遍历来实现常量空间，但排序通常是 \(O(n \log n)\) 的时间复杂度。

要使用常量内存实现 mystery() 方法，假设每个整数在数组中最多出现两次，我们可以采用以下思路：

  1. 使用原地修改数组：我们将利用数组的索引来记录元素的出现次数。通过对数组元素进行标记，我们可以判断一个元素是否已经出现过两次。

  2. 遍历数组并标记：遍历数组时，使用元素的值作为索引，标记其出现次数。由于每个整数最多出现两次，我们可以用负值来标记。

下面是实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static boolean mystery(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int index = Math.abs(array[i]); // 取当前值的绝对值作为索引
        if (index >= array.length) {
            continue; // 确保索引在有效范围内
        }
        
        // 根据当前值的符号判断出现次数
        if (array[index] < 0) {
            // 已经出现过两次，返回 false
            return false;
        }
        
        // 标记出现次数，取反
        array[index] = -array[index];
    }

    // 恢复数组（可选，若需要保留原始数组，可在此添加恢复逻辑）
    for (int i = 0; i < array.length; i++) {
        array[i] = Math.abs(array[i]); // 恢复原始值
    }
    
    return true; // 所有值都最多出现两次
}
2.3 运行时间分析

假设 comeOn() 的时间复杂度为 (1) ，并返回布尔值。

1
2
3
4
5
6
7
8
9
for (int i = 0; i < N; i++) {
    for (int j = 1; j <= M; ) {
        if (comeOn()) {
            j += 1;
        } else {
            j *= 2;
        }
    }
}
  • 最坏情况: \(\Theta(NM)\)
  • 最好情况: $ (N M)$
    说明: 在最佳情况下，comeOn() 始终返回假，因此 $ j$ 每次翻倍。内部循环相对于 $ M$ 执行，外部循环迭代 $ N $ 次。

3 有趣的算法

3.1 找到和为 x 的索引

给定整数 \(x\) 和排序数组 \(A\) 的 N 个不同整数，设计一个算法检查是否存在索引 \(i\) 和 $ j$ ，使得 \(A[i] + A[j] == x\) 。

朴素解法：

1
2
3
4
5
6
7
8
9
10
public static boolean findSum(int[] A, int x) {
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < A.length; j++) {
            if (A[i] + A[j] == x) {
                return true;
            }
        }
    }
    return false;
}

(a) 如何改进这个解决方案？
使用两个指针，分别从数组的两端向中间移动：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static boolean findSumFaster(int[] A, int x) {
    int left = 0;
    int right = A.length - 1;
    while (left <= right) {
        if (A[left] + A[right] == x) {
            return true;
        } else if (A[left] + A[right] < x) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

(b) 两种算法的运行时间：

  • 朴素解法: 最坏情况 \(\Theta(N^2)\) ，最好情况 $ (1) $。
  • 优化解法: 最坏情况 \(\Theta(N)\) ，最好情况 $(1) $。

4 CTCI 额外问题

4.1 并集

编写代码，返回两个给定数组的并集。并集是包含两个数组中所有元素的列表，没有重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int[] union(int[] A, int[] B) {
    HashSet<Integer> set = new HashSet<Integer>();
    for (int num : A) {
        set.add(num);
    }
    for (int num : B) {
        set.add(num);
    }
    int[] unionArray = new int[set.size()];
    int index = 0;
    for (int num : set) {
        unionArray[index] = num;
        index += 1;
    }
    return unionArray;
}

提示: 方法的时间复杂度应为 $O(M + N) $，其中 \(M\) 和 \(N\) 是每个数组的大小。

4.2 交集

同样的操作，找到两个数组的交集。交集是两个数组中所有共同元素的列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int[] intersection(int[] A, int[] B) {
    HashSet<Integer> setOfA = new HashSet<Integer>();
    HashSet<Integer> intersectionSet = new HashSet<Integer>();
    for (int num : A) {
        setOfA.add(num);
    }
    for (int num : B) {
        if (setOfA.contains(num)) {
            intersectionSet.add(num);
        }
    }
    int[] intersectionArray = new int[intersectionSet.size()];
    int index = 0;
    for (int num : intersectionSet) {
        intersectionArray[index] = num;
        index += 1;
    }
    return intersectionArray;
}