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

公式复习

在进行渐近分析时，以下公式可能会对你有所帮助：

$\sum_{i=1}^{N} i = 1 + 2 + 3 + 4 + \dots + N = \frac{N(N+1)}{2} = \frac{N^2 + N}{2}$
$\sum_{i=0}^{N-1} 2^i = 1 + 2 + 4 + 8 + \dots + 2^{N-1} = 2^N - 1$

分析递归函数的直觉

对于以下递归函数，给出其在最坏情况和最好情况下的运行时间，使用适当的 $O(·), Ω(·) 或 Θ(·) $表示法。

分析递归程序的元策略：

递归树的高度。
每个节点的分支因子。
每个节点相对于输入大小的工作量。

1.1 递归函数 `andslam(int N)` 的时间复杂度

public void andslam(int N) {
    if (N > 0) {
        for (int i = 0; i < N; i += 1) {
            System.out.println("datboi.jpg");
        }
        andslam(N / 2);
    }
}

分析：

在每次递归调用中，函数会执行一个 for 循环，时间复杂度为 O(N)。
然后，它递归调用 andslam(N/2)。
递归调用的次数为 $\log N$，因为每次输入大小减半。
总的来说，时间复杂度为： $T(N) = N + N/2 + N/4 + \dots = 2N$

因此，andslam(N) 的运行时间在最好和最坏情况下都是 Θ(N)。

1.2 递归函数 `andwelcome(int[] arr, int low, int high)` 的时间复杂度

public static void andwelcome(int[] arr, int low, int high) {
    System.out.print("[ ");
    for (int i = low; i < high; i += 1) {
        System.out.print("loyal ");
    }
    System.out.println("]");
    if (high - low > 0) {
        double coin = Math.random();
        if (coin > 0.5) {
            andwelcome(arr, low, low + (high - low) / 2);
        } else {
            andwelcome(arr, low, low + (high - low) / 2);
            andwelcome(arr, low + (high - low) / 2, high);
        }
    }
}

分析：

在每次递归调用中，函数会遍历数组，时间复杂度为 $O(N)$。
最坏情况：每次随机数 coin 使得递归树分支成 2 个，递归调用的次数为 $\log N$。
最好情况：递归树只有一个分支，即递归调用的次数是线性的。
递归关系：
- 最坏情况：$T(N) = 2T(N/2) + O(N)$，时间复杂度为 Θ(N log N)。
- 最好情况：$T(N) = T(N/2) + O(N)$，时间复杂度为 Θ(N)。

1.3 递归函数 `tothe(int N)` 的时间复杂度

public int tothe(int N) {
    if (N <= 1) {
        return N;
    }
    return tothe(N - 1) + tothe(N - 1);
}

分析：

这是一个典型的二叉递归，每次调用都递归两次，且每次的输入大小减小 1。
递归树的高度为 N，且每一层的节点数是 2 的幂次（第 i 层有 $2^i$ 个节点）。
因为每个节点做常量时间的工作，整个树的节点总数是 $2^N - 1$。

因此，tothe(N) 的时间复杂度为 $Θ(2^N)$（最坏和最好情况都是一样的）。

1.4 递归函数 `spacejam(int N)` 的时间复杂度

public static void spacejam(int N) {
    if (N <= 1) {
        return;
    }
    for (int i = 0; i < N; i += 1) {
        spacejam(N - 1);
    }
}

分析：

这是一个嵌套递归，每次调用都会执行一个循环，且每次递归调用的输入大小减小 1。
在第 i 层的分支因子是$ N - i$，形成一个阶乘的模式。
总的时间复杂度为： $T(N) = N \cdot (N - 1) \cdot \dots \cdot 1 = N!$

因此，spacejam(N) 的时间复杂度为 $O(N \cdot N!)$（最坏和最好情况都是相同的）。

2.1 两个算法的比较

算法1：$Θ(N)$，算法2：$Θ(N^2)$

算法1一定比算法2快，因为线性复杂度比平方复杂度低。

算法1：$Ω(N)$，算法2：$Ω(N^2)$

不能确定哪个更快，因为 Ω 表示下界，不能确定算法1的上界。

算法1：$O(N)$，算法2：$O(N^2)$

不能确定哪个更快，因为 O 表示上界，算法2的运行时间可能会低于 $N^2$。

算法1：$Θ(N^2)$，算法2：$O(log N)$

算法2一定比算法1快，因为 $log N $增长速度比 $N^2 $慢。

算法1：$O(N log N)$，算法2：$Ω(N log N)$

无法确定哪个更快，两个算法可能在不同情况下表现相同。

注意：在输入规模较小时（例如 N 是常数），运行时间的常数和低阶项可能主导算法的表现，但渐近符号（O, Ω, Θ）假设的是大规模输入。

渐近符号总结

O(·)：上界，表示算法的运行时间不会比某个函数增长得更快。
Ω(·)：下界，表示算法的运行时间不会比某个函数增长得更慢。
Θ(·)：精确界，表示算法的运行时间与某个函数的增长速度相同。