CS61B 课程笔记（Examprep 07 Asymptotic Analysis Exam I Prep)

CS 61B 抽象数据类型

1. 开始（2017年春季，MT2）

填空题：为每个代码块填入空白，以便函数具有所需的运行时间。

函数 f1：期望运行时间：$Θ(N)$
1
2
3
4
5
public static void f1(int N) {
for (int i = 1; i < N; i += 1) {
System.out.println("hi");
}
}
解释：
- 该循环执行了N-1次（从1到N-1），每次打印操作的时间复杂度为O(1)。
- 总时间复杂度为： $ T(N) = _{i=1}^{N-1} O(1) = O(N) $
- 因此，运行时间为Θ(N)。
函数 f2：期望运行时间：Θ(log N)
1
2
3
4
5
public static void f2(int N) {
for (int i = 1; i < N; i *= 2) {
System.out.println("hi");
}
}
解释：
- 循环中，i的值依次为$1, 2, 4, 8, ..., 2^k$，直到$i < N$。
- k的最大值满足 ($2^k < N$)，因此： $ k < _2(N) k = _2(N) $
- 总的迭代次数为$Θ(log N)$。
函数 f3：期望运行时间：Θ(1)
1
2
3
4
5
public static void f3(int N) {
for (int i = 1; i < N; i += N) {
System.out.println("hi");
}
}
解释：
- 循环的步长为$N$，所以仅执行一次（如果$N>1$）。
- 因此，总运行时间为常量时间$Θ(1)$。

2. 稍微困难（2017年春季，MT2）

运行时间分析：给出以下函数的运行时间，用$Θ$或$O$表示，答案应尽量简单。

函数 f4：
1
2
3
4
5
6
7
8
public static void f4(int N) {
if (N == 0) { return; }
f4(N / 2);
f4(N / 2);
f4(N / 2);
f4(N / 2);
g(N); // 运行时间为Θ(N²)
}
答案：Θ(N² log N) 解释：
- 函数f4的递归关系为： $ T(N) = 4T() + Θ(N^2) $
- 根据主定理：
  - ($a = 4$), ($b = 2$), ($f(N) = Θ(N^2)$)
  - ($N^{\log_b a} = N^{\log_2 4} = N^2$)
  - 因为 ($f(N)$) 和 ($N^{\log_b a}$) 的增长速率相同，所以可以应用主定理的情况2。
- 最终得出： $ T(N) = Θ(N^2 N) $
函数 f5：
1
2
3
4
5
6
7
public static void f5(int N, int M) {
if (N < 10) { return; }
for (int i = 0; i <= N % 10; i++) {
f5(N / 10, M / 10);
System.out.println(M);
}
}
答案：$O(N)$ 解释：
- 每次递归将$N$减少一个数字，因此递归深度为$Θ(N)$。
- 每次调用处理一个常量的打印操作，所以每层递归的运行时间为$O(1)$。
- 总运行时间为： $ T(N) = O(1) + T(N-1) + O(1) + $
- 结果为O(N)。

3. 更多，更多，更多（2016年春季，MT2）

为以下代码块提供运行时间的$Θ(·)$表示，作为N的函数。

函数 p1：

public static void p1(int N) {
    for (int i = 0; i < N; i += 1) {
        for (int j = 1; j < N; j = j + 2) {
            System.out.println("hi !");
        }
    }
}

答案：$Θ(N²)$ 解释：

外层循环运行N次，内层循环从1到N，每次增加2，运行次数为N/2。
总时间为： $ T(N) = N = = Θ(N^2) $

函数 p2：

public static void p2(int N) {
    for (int i = 0; i < N; i += 1) {
        for (int j = 1; j < N; j = j * 2) {
            System.out.println("hi !");
        }
    }
}

答案：$Θ(N log N)$ 解释：

外层循环运行N次，内层循环以2为底的对数次数运行： $ T(N) = N O(_2 N) = Θ(N N) $

函数 p3：
1
2
3
4
5
public static void p3(int N) {
if (N <= 1) return;
p3(N / 2);
p3(N / 2);
}
答案：$Θ(N)$ 解释：
- 递归树的深度为$log(N)$，每层处理的数量为$N$，因此： $ T(N) = 2T() T(N) = O(N) $

函数 p4：

public static void p4(int N) {
    int m = (int)((15 + Math.round(3.2 / 2)) * 
        (Math.floor(10 / 5.5) / 2.5) * Math.pow(2, 5));
    for (int i = 0; i < m; i++) {
        System.out.println("hi");
    }
}

答案：$Θ(1)$ 解释：

计算m的过程是常量时间，因为没有依赖于$N$的计算。循环$m$次，但$m$是常量，所以： $ T(N) = Θ(1) $

函数 p5：
1
2
3
4
5
6
7
public static void p5(int N) {
for (int i = 1; i <= N * N; i *= 2) {
for (int j = 0; j < i; j++) {
System.out.println("moo");
}
}
}
答案：$Θ(N²)$ 解释：
- 外层循环迭代次数为$log(N²)$，内层循环在外层的每次迭代中迭代$i$次，随着i的增长（$1, 2, 4, ..., N²$）： $ T(N) = O(1) + O(2) + O(4) + + O(N^2) = Θ(N^2) $

4. 野生的 Hilfinger 出现！（2017年秋季，期末考试）

最坏情况运行时间分析：答案：$Θ(N²)$ 解释：
- 递归调用$r$的深度与$M$成正比，而$s$的调用也在每次递归中遍历$k$的所有可能，导致总体复杂度为$Θ(N²)$。
最坏情况运行时间分析：答案：$Θ(N²)$ 解释：
- 外层循环的迭代次数为$M$，内层循环的迭代次数为线性关系，因此整体复杂度为$Θ(N²)$。