CS61B 课程笔记（Disc 08 Asymptotic Analysis II)

1. 热身题

题目：给定以下方法在一个排序数组上查找元素，问其最坏情况下的运行时间是多少？是否有改进方法？改进后最坏情况下的运行时间是多少？

public static int f1(int i, int[] numList) {
    for (int j = 0; j < numList.length; j++) {
        if (numList[j] == i) {
            return j;
        }
    }
    return -1;
}

解答：

最坏情况分析：最坏情况下，算法遍历整个 numList，因此其最坏时间复杂度为 $ (N) $，其中 N 为数组中的元素数量。
优化方法：由于数组是有序的，可以使用二分查找，将时间复杂度降低为 $\Theta(\log N)$ （最坏情况）。

public static int binarySearch(int i, int[] numList) {
    int left = 0;
    int right = numList.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (numList[mid] == i) {
            return mid; // 找到目标元素，返回其索引
        } else if (numList[mid] < i) {
            left = mid + 1; // 目标元素在右半部分
        } else {
            right = mid - 1; // 目标元素在左半部分
        }
    }

    return -1; // 如果未找到，返回 -1
}

解释：

初始化边界：我们初始化两个指针 left 和 right，分别指向数组的开始和结束。
中间元素检查：每次迭代时，我们通过 mid = left + (right - left) / 2 计算中间索引，然后检查该位置的元素：
- 如果中间元素等于目标元素，直接返回索引。
- 如果中间元素小于目标元素，说明目标在右半部分，因此将 left 移动到 mid + 1。
- 如果中间元素大于目标元素，说明目标在左半部分，因此将 right 移动到 mid - 1。
结束条件：当 left > right 时，表示数组中没有目标元素，返回 -1。

优化后时间复杂度：

该算法的时间复杂度为 $\Theta(\log N)$ ，因为每次迭代都会将搜索范围缩小一半。

2. 递归算法分析

代码 1：

public static void f1(int n) {
    if (n == 0) {
        return;
    }
    f1(n / 2);
    f(n);
    f1(n / 2);
}

运行时间：每次递归调用分成两部分，每层调用执行的工作量为 $O(n)$ ，总共有 $\log n$ 层。因此，整个算法的时间复杂度为 $\Theta(n \log n)$ 。

要理解这个递归算法的时间复杂度为 $ (n n) $，我们可以通过递归树分析的方法一步步拆解。

代码分析：
1
2
3
4
5
6
7
8
public static void f1(int n) {
    if (n == 0) { 
        return; 
    }
    f1(n / 2);   // 递归调用自身，规模减半
    f(n);        // 假设 f(n) 的时间复杂度为 O(n)
    f1(n / 2);   // 再次递归调用自身，规模减半
}
关键点：

递归调用 f1(n / 2) 意味着问题规模每次减半。

每次调用函数 f(n)，其时间复杂度是 O(n) 。

递归调用两次 f1(n / 2)，问题继续分成更小的子问题。

递归树分析：

1. 每层的工作量：

在递归的每一层，f(n) 是一个占用 $O(n) $ 时间的操作。因此，每一层的工作量为 $ O(n)$ 。

2. 递归的层数：

由于每次递归调用的参数变为原来的 $ $ ，即问题规模每次缩小一半，这意味着递归树的层数为 $ n $ 层（这是因为我们继续对问题规模减半直到问题规模为 0）。

3. 每层的工作分析：

第一层：工作量是 $ O(n) $。

第二层：调用两次 f1(n/2)，每次调用的工作量是 $O(n/2)$ 。由于有两个子问题，总工作量为 $2 O(n/2) = O(n) $。

第三层：调用四次 f1(n/4)，每次调用的工作量是 $O(n/4) $，总工作量为 $4 O(n/4) = O(n) $。

以此类推，每层的工作量都是 $ O(n)$ 。

4. 总工作量：

每一层的工作量为 $ O(n) $，而总共有 $ n$ 层。

因此，总的工作量为 $O(n) n $，即总时间复杂度为 $(n n) $。

总结：

递归树的层数为 $ n$ ，因为每次递归将问题规模减半。

每层的工作量是 $O(n) $，因为每层都调用了线性时间复杂度的函数 $ f(n)$ 。

因此，整个递归的时间复杂度为 $\Theta(n \log n)$ 。

代码 2：

public static void f2(int n) {
    if (n == 0) {
        return;
    }
    f2(n - 1);
    f(17);
    f2(n - 1);
}

运行时间：递归的每层都执行两次递归调用，并且每次递归深度是 $n $。总共有 $2^n$ 个叶子节点，因此时间复杂度为 $\Theta(2^n)$ 。

为了理解代码 2 的时间复杂度为 $(2^n) $，我们可以同样通过递归树的分析方法来一步步拆解。

代码分析：
1
2
3
4
5
6
7
8
public static void f2(int n) {
    if (n == 0) { 
        return; 
    }
    f2(n - 1);  // 递归调用1，问题规模减小为 n - 1
    f(17);      // 假设 f(17) 是常数时间复杂度 O(1)
    f2(n - 1);  // 递归调用2，问题规模减小为 n - 1
}
关键点：

f2(n - 1) 表示每次递归调用时，问题的规模减小 1。

每次调用 f(17) 都是常数时间操作，时间复杂度为 $O(1)$ 。

递归调用两次 f2(n - 1)，意味着问题会继续拆解成两个子问题。

递归树分析：

1. 每层的工作量：

在递归的每一层，递归调用 f2(n - 1) 两次，每次调用 f(17) 的时间复杂度是 $ O(1) $。

2. 递归的层数：

因为问题规模每次减小 1，递归树的层数为 n 层（递归从 n 一直递减到 0，共 n 次）。

3. 递归树的结构：

第一层：有 1 个节点（根节点）调用 f2(n)。

第二层：有 2 个节点，分别是 f2(n-1) 的两个递归调用。

第三层：有 4 个节点，分别是每个 f2(n-2) 的两个递归调用。

以此类推，每层的节点数翻倍，第 k 层有 $2^k$ 个节点。

4. 递归树的节点总数：

递归树的总节点数为 $1 + 2 + 4 + \dots + 2^{n-1}$ ，这是一个等比数列，其总和为 $ 2^n - 1 $。

递归树的叶子节点总数为 $2^n$ ，因为在最后一层，所有递归调用都达到基准条件 $n = 0 $ 而停止。

5. 总工作量：

每个节点调用 f(17)，时间复杂度为 $O(1)$ 。

递归树的总节点数为 $2^n - 1 $，每个节点的工作量为 $O(1)$ ，因此总的工作量是 $O(2^n) $。

递归时间复杂度分析总结：

递归树有 $n$ 层，节点数呈指数增长，每层的节点数是前一层的两倍。

每个节点的工作量是常数 $O(1)$ ，但总的节点数为 $2^n$ ，因此总的工作量是 $(2^n) $。

总结：

这个递归算法的时间复杂度是 $\Theta(2^n)$ ，因为递归树有 $2^n $ 个节点，每个节点执行常数时间的工作 $O(1) $。

代码 3：

public static void f3(int n, int m) {
    if (m <= 0) {
        return;
    } else {
        for (int i = 0; i < n; i += 1) {
            f3(n, m - 1);
        }
    }
}

运行时间：该代码是前一个递归的广义形式，递归深度是 $ m$ ，每次递归调用 $n$ 次。因此，时间复杂度为 $\Theta(n^m$) 。

为了详细理解代码 3 的时间复杂度为 (n^m) ，我们同样使用递归树分析法。

代码分析：
1
2
3
4
5
6
7
8
9
public static void f3(int n, int m) {
    if (m <= 0) {
        return; // 基准条件，当 m <= 0 时停止递归
    } else {
        for (int i = 0; i < n; i += 1) { 
            f3(n, m - 1); // 递归调用，问题规模缩小到 m - 1
        }
    }
}
关键点：

递归结构：

当 m > 0 时，函数 f3(n, m) 会进行一个 for 循环，循环体内调用 n 次 f3(n, m - 1)。

当 m = 0 时，递归停止，即函数直接返回。

每次递归深度 m 减少 1，而每次递归时会调用 n 次 f3(n, m - 1)。

递归树的深度：

递归的深度是 m ，因为每次递归调用时 m 都减少 1，直到 m = 0 为止。

递归树分析：

第一层：

初始调用是 f3(n, m)，这一层会有 1 次函数调用。

在这一层，执行 for 循环 n 次，每次递归调用 f3(n, m-1)。

第二层：

第二层有 n 次递归调用，每次调用 f3(n, m-1)。

每个递归调用再次执行 n 次递归调用 f3(n, m-2)。

第三层：

第三层有 $n \times n = n^2$ 次递归调用，每次调用 f3(n, m-2)。

每个调用再次执行 n 次递归调用 f3(n, m-3)。

以此类推，直到递归深度达到 m ，每层的递归调用数成倍增加。

递归树的节点总数：

每一层的递归调用数为：

第 1 层有 $1$ 个调用，

第 2 层有 $n$ 个调用，

第 3 层有 $n^2$ 个调用，

第 4 层有 $n^3 $ 个调用，

$\dots$，直到第 $m$ 层有 $n^{m-1}$ 个调用。

整个递归树共有 $m $ 层。

总的递归调用数等于递归树所有节点的总和，这可以表示为一个等比数列： $1 + n + n^2 + \dots + n^{m-1} = \frac{n^m - 1}{n - 1}$

忽略常数项，节点总数的量级为 $n^m $，即递归树的大小为 $ O(n^m)$ 。

每个节点的工作量：

每个递归调用的 for 循环本身只执行常数时间的工作 $O(1)$ 。

因此，每个节点的工作量为 O(1) ，总工作量由节点数 $O(n^m) $ 决定。

时间复杂度分析总结：

递归树的总节点数为 $O(n^m)$ ，每个节点的工作量为 $O(1) $，所以总时间复杂度为：$(n^m)$

总结：

代码 3 的递归结构使得每次递归会生成 $n$ 个新的递归调用，且递归的深度为 $m$ 。由于每一层递归的调用数呈现指数增长，递归树的总节点数为 $n^m $，最终算法的时间复杂度为 $(n^m) $。

3. 代码分析

代码分析 1：

public static void foo2(int i, int N) {
    if (i == 0) {
        return;
    }
    for (int j = 0; j < i; j++) {
        cnst();
    }
    if (i > N / 2) {
        foo2(i - 1, N);
    } else {
        foo2(i / 2, N);
        foo2(i / 2, N);
    }
}

最坏情况：无论是递归减小 $ i $，还是二分递归，代码整体的时间复杂度都与 $N$ 的平方相关。因此最坏情况下的运行时间是 $ (N^2)$ 。
最好情况：由于递归结构在最佳情况下也可能达到平方级的复杂度，最佳情况时间复杂度同样是 $\Theta(N^2)$ 。

让我们详细分析代码并解释为什么该算法在最坏和最好情况下的时间复杂度都是 $ (N^2)$ 。

代码结构分析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void foo2(int i, int N) {
    if (i == 0) {
        return; // 基准条件
    }
    // 1. 执行 `i` 次常数时间操作
    for (int j = 0; j < i; j++) {
        cnst();
    }
    // 2. 递归调用
    if (i > N / 2) {
        foo2(i - 1, N); // 递归调用一次，减少 1
    } else {
        foo2(i / 2, N); // 二分递归两次
        foo2(i / 2, N);
    }
}
分析步骤：

for 循环的工作量：

每次调用 foo2 时，for 循环执行 i 次常数操作（假设 cnst() 是常数时间操作）。

因此，for 循环的工作量为 O(i) 。

递归的结构：

当 i > N/2 时，递归调用一次，即 foo2(i - 1, N)，问题规模减少 1。

当 i N/2 时，递归调用两次 foo2(i / 2, N)，问题规模减小为原来的一半。这类似二叉树递归。

最坏情况分析：

在最坏情况下，每次递归都遵循 $i > N/2$ 的条件，递归只减小 1。

当 $i = N$ 时：

第一次调用 foo2(N - 1, N)，循环执行 N 次操作。

第二次调用 foo2(N - 2, N)，循环执行 N-1 次操作。

以此类推，总共执行的操作次数是： $N + (N-1) + (N-2) + \dots + 1 = \frac{N(N+1)}{2}$

这是一个等差数列的和，时间复杂度为 $ O(N^2)$ 。

因此，在最坏情况下，当递归每次只减 1 时，总的时间复杂度为 $ (N^2) $。

最好情况分析：

在最好情况下，每次递归都遵循 $ i N/2 $ 的条件，递归两次并将 i 的规模减半。

递归树：

在每个递归步骤中，当 $ i N/2 $ 时，函数会递归两次 foo2(i / 2, N)。

这形成了一个递归树，树的深度为 $O(N) $，因为每次递归将 $ i$ 减半。

每层工作量：

在递归树的每一层，总工作量为当前层的节点数乘以每个节点的工作量。

第 1 层有 1 个节点，执行 N 次 for 循环；

第 2 层有 2 个节点，每个节点执行 N/2 次 for 循环；

第 3 层有 4 个节点，每个节点执行 N/4 次 for 循环；

以此类推，直到第 $\log N$ 层。

总工作量：

每层的工作量是 $ N$ ，因为： $1 \times N + 2 \times \frac{N}{2} + 4 \times \frac{N}{4} + \dots = N$

总共有 N 层，因此总的工作量是 $O(N \log N)$ 。

但是，递归树并不总是保持均匀分布。即使在最好情况下，也可能存在某些递归分支会执行额外的工作，导致递归树的工作量加剧。

因此，即使在最好情况下，递归结构和 for 循环的结合可能仍会产生平方级的复杂度，导致总的时间复杂度为 $\Theta(N^2$) 。

结论：

无论是最坏情况还是最好情况，代码中的递归结构和 for 循环的执行量最终都导致了时间复杂度为 $ (N^2) $。

4. 判定题

题目 1：如果 $ f(N) O(N)$ 且 $g(N) O(N^2) $，两者均为非负函数，那么 $|g(N) - f(N)| (N) $ 是否成立？

答案：错误。反例：令 $ f(N) = g(N) = N $，则两者的差为 0，不能用 N 作为下界。
题目 2：如果 $f(N) \in \Theta(N$) 且 $g(N) \in \Theta(N^2)$，两者均为非负函数，那么 $|g(N) - f(N)| (N) $ 是否成立？

答案：正确。因为 $g(N) $ 的增长率为 $N^2 $，远大于 $ f(N)$ ，因此差值的下界可以由 $N$ 确定。

符号解释

** O(N) **: 表示函数的上界。即存在常数 $C > 0$ 和 $N_0$ 使得对于所有 $N N_0 $，有 $ f(N) C N$ 。

** $\Omega(N)$ **: 表示函数的下界。即存在常数 $c > 0 $ 和 $N_0$ 使得对于所有 $N N_0 $，有 $ g(N) c N $。

** $\Theta(N)$ **: 表示函数的紧确界，既有上界也有下界。即 $ f(N) O(N)$ 且 $f(N) \in \Omega(N)$ ，也就是说，存在常数 $C_1, C_2 > 0 $ 和 $ N_0 $，使得对于所有 $N N_0 $，有 $C_1 N f(N) C_2 N $。

题目分析

题目 1

条件: $ f(N) O(N)$ 且 $ g(N) O(N^2)$

这表示 $ f(N)$ 的增长速度最多是线性的，而 $g(N)$ 的增长速度最多是平方的。

需要验证的是 $|g(N) - f(N)| \in \Omega(N)$ 。

反例: 令 $f(N) = N$ 和 $g(N) = N$

在这种情况下， $|g(N) - f(N)| = |N - N| = 0 $。

由于 0 不能满足下界 $ c N $ 的条件，因此这个例子证明了题目是错误的。

所以，题目 1 的答案是错误的，因为可以构造出 $g(N)$ 和 $f(N)$ 使得它们的差是0，不满足 $|g(N) - f(N)| \in \Omega(N)$ 。

题目 2

条件: $f(N) \in \Theta(N)$ 且 $g(N) (N^2) $

这里 $f(N)$ 的增长速度是线性的，而 g(N) 的增长速度是平方的。

我们需要验证 $ |g(N) - f(N)| (N) $。

分析:

由于 $g(N) \in \Theta(N^2)$ ，我们知道存在常数 $C_1 > 0 $ 使得 $ g(N) C_1 N^2 $。

而 $f(N) \in \Theta(N)$ 表示 $f(N)$ 增长速度较慢，最多是线性。

因此，随着 $N $ 的增加，$ g(N) $ 的值远大于$ f(N) $，即 $g(N) - f(N) $ 仍然接近 $ g(N)$ 。

对于足够大的 N ，我们可以得到： $|g(N) - f(N)| = g(N) - f(N) \geq C_1 \cdot N^2 - C_2 \cdot N \quad (\text{对于某些常数 } C_2)$

当 N 足够大时，$ C_1 N^2 $ 的影响远大于 $C_2 N $，因此：$|g(N) - f(N)| c N c > 0 $

这意味着 $|g(N) - f(N)| (N) $。

因此，题目 2 的答案是正确的，因为 $g(N)$ 的增长速度远大于 $ f(N)$ ，使得两者的差的下界由 N 确定。

总结

题目 1: 错误。反例为 $f(N) = N$ 和 $g(N) = N$ ，其差为0。

题目 2: 正确。由于 $g(N)$ 的增长速度大于 $ f(N)$ ，确保了它们之间的差的下界是 $\Omega(N)$ 。

5. 算法分析

代码 1：

/** 假设 VALS 是一个二维数组，且 0 <= R, C < vals.length。 */
double best(double vals[][], int r, int c) {
    if (r == 0) {
        return vals[r][c];
    }
    double v = best(vals, r - 1, c);
    if (c > 0) {
        v = Math.max(v, best(vals, r - 1, c - 1));
    }
    if (c < vals[r].length - 1) {
        v = Math.max(v, best(vals, r - 1, c + 1));
    }
    return v + vals[r][c];
}

最坏情况：每次递归有 $3$ 个递归调用，深度为 $r $，所以递归树的每一层有 $3$ 的幂次个节点，最终的时间复杂度为 $O(3^r) $。

6. 改进数据结构

题目：你的朋友每天遇到成百上千的人，并将他们的名字放在 ArrayList 的开头。他从未删除名字，有时会查看人们见面的顺序。描述一个小改动，改进数据结构的使用以提升性能，并解释原因。

解答：在 ArrayList 开头插入元素的成本较高，因为需要将所有元素后移 1 位，时间复杂度为线性时间操作。改为在末尾插入可以提高效率。
进一步优化：使用 LinkedList，可以在前面常数时间内插入元素，优化操作的运行时间。

7. 递归复杂度分析

代码 1：

public int f1(n) {
    if (n == 1) {
        return 0;
    }
    if (n 是偶数) {
        return f3(n / 2);
    } else {
        return f3(n + 1);
    }
}

时间复杂度：每次递归将问题规模减半，因此总时间复杂度为 $ (N)$ 。

代码 2：

function f2(n) {
    if (n == 1) {
        return 1;
    }
    int a = f2(n / 2);
    int b = f2(n / 2);
    x = process(a, b);
    return x;
}

时间复杂度：process() 运行在 $\Theta(n \log n)$ ，递归树的每一层都执行 $n \log n$ 的工作，总共有 $\log^2 n$ 层，因此总时间复杂度为 $\Theta(n \log^2 n)$ 。

代码分析

以下是提供的递归函数 f2 的定义：
1
2
3
4
5
6
7
8
9
function f2(n) {
    if (n == 1) {
        return 1;
    }
    int a = f2(n / 2);
    int b = f2(n / 2);
    x = process(a, b);
    return x;
}
时间复杂度分析
递归树结构:

当 n > 1 时，函数 f2 会调用自身两次，每次的参数是 $n/2 $。

递归树的每一层都有两个子调用，因此递归树的结构为：
1
2
3
4
5
6
7
f2(n)
├── f2(n/2)
│   ├── f2(n/4)
│   └── f2(n/4)
└── f2(n/2)
    ├── f2(n/4)
    └── f2(n/4)
继续这个过程，会看到树的深度是 $n $，因为每次调用的输入大小都减小了一半。
每一层的工作量:

每一层的工作量由 process(a, b) 决定，假设 process 的时间复杂度为 $\Theta(n \log n)$ 。

因此，每一层的工作量是 $(n n) $。

层数:

递归树的高度为 $ n$ ，即深度为 $\log n$ 。

总的工作量:

每一层的工作量是 $ (n n) $，并且有 $ n$ 层，因此总的工作量是： $ T(n) = = (n n) n = (n ^2 n)$
结论

通过上面的分析，我们得出了总时间复杂度为 $(n ^2 n) $ 的结论。这个复杂度来源于递归树的层数和每一层的工作量相乘。每层都有 $n \log n$ 的工作，而层数为 $ n$ ，因此总时间复杂度是 $\Theta(n \log^2 n)$ 。

8. 判定题

题目：如果 $f(n) = O(g(n))$ ，那么 $2^{f(n)} = O(2^{g(n)}) $ 是否成立？

答案：错误。反例：设 $ f(n) = n$ ， $g(n) = n / 2 $，通过指数操作可以得出不同的结果。

CS61B 课程笔记（Disc 08 Asymptotic Analysis II)

1. 热身题

解释：

优化后时间复杂度：

2. 递归算法分析

代码分析：

关键点：

递归树分析：

1. 每层的工作量：

2. 递归的层数：

3. 每层的工作分析：

4. 总工作量：

总结：

代码分析：

关键点：

递归树分析：

1. 每层的工作量：

2. 递归的层数：

3. 递归树的结构：

4. 递归树的节点总数：

5. 总工作量：

递归时间复杂度分析总结：

总结：

代码分析：

关键点：

递归树分析：

递归树的节点总数：

每个节点的工作量：

时间复杂度分析总结：

总结：

3. 代码分析

代码结构分析：

分析步骤：

最坏情况分析：

最好情况分析：

结论：

4. 判定题

符号解释

题目分析

题目 1

题目 2

总结

5. 算法分析

6. 改进数据结构

7. 递归复杂度分析

代码分析

时间复杂度分析

结论

8. 判定题