注：本文原文为英语，由ChatGPT翻译成中文。

计算$\Theta (f(N))$的技巧

示例1：一个For循环

1
2
3
4
5
6

int N = A.length;
for (int i = 0; i < N; i += 1)
   for (int j = i + 1; j < N; j += 1)
      if (A[i] == A[j])
         return true;
return false;
  1. 方法1：计算操作次数（精确计数）

“==“操作的总成本/操作次数为： $$ C(N)=1+2+3+\dots+(N-2)+(N-1) = \frac{N(N-1)}{2} $$ 因此，运行时间为$\Theta (N^2)$。

  1. 方法2：几何可视化

（想象彩色方块-由于是一个三角形区域-运行时间为$\Theta (N^2)$。）

示例2：另一个For循环

1
2
3
4
5
6
7
8

public static void printParty(int N) {
   for (int i = 1; i <= N; i = i * 2) {
      for (int j = 0; j < i; j += 1) {
         System.out.println("hello");   
         int ZUG = 1 + 1;
      }
   }
}
  1. 方法1：通过可视化找到界限

绘制0.5N（下方虚线）和4N（上方虚线）的轨迹

C(N)将位于这两条线之间

因此，运行时间为$\Theta (N)$。

（个人认为这种方法不如数学方法直观。）

  1. 方法2：通过数学方法找到界限

想象一下方框：

基于简化的几何分析

因此，$C(N)$将为： $$ C(N)=1+2+4+\dots+N= 2N-1 $$ 因此，运行时间为$\Theta (N)$。

示例3：树递归

1
2
3
4
5

public static int f3(int n) {
   if (n <= 1) 
      return 1;
   return f3(n-1) + f3(n-1);
}
  1. 方法1：直觉

每次将n增加1，工作量加倍

…这导致运行时间直观上为$2^N$。

树递归

  1. 方法2：代数

$C(N)$的成本为： $$ C(N) = 1+2+4+\dots+2^\left(N-1\right)=2^N-1 $$ 因此，运行时间为$\Theta (2^N)$。

  1. 方法3：递归关系（超出范围）

从以下开始： $$ C(N)=2C(N-1)+1 $$

示例4：二分查找

二分查找

  1. 方法1：直觉

我们从N个选项开始，然后N/2，然后N/4 … 直到只剩下1个。

每次，我们将数组分成两半，因此最后我们必须执行总共$\log_{2}(N)$次操作…

因此，总体运行时间为$\Theta (\log(N))$。

  1. 方法2：精确计数
二分查找

因此，$C(N)=\left\lfloor \log_{2}(N) \right\rfloor + 1$（根据观察）。

运行时间为$\Theta(\log(N))$。

示例5：归并排序

  • 任意时间单位：相对的时间需求

例如，如果我们运行N=6的选择排序，运行时间的阶数为$N^2$，那么运行时间将为约36个AU。

  • 关于归并排序-一个简单的情况（将两个列表合并为一个）
归并排序

其运行时间为$\Theta (N)$。

  • 归并排序-将归并排序应用于排序一个长列表
归并排序

关键思想是将原始数组分割成最小的片段，并应用归并排序（其运行时间为$\Theta (N)$）。

因此，归并排序的最坏情况运行时间为$\Theta (N \cdot \log(N))$，其中

最上层花费约N个AU。

下一层花费约N/2 + N/2 = N个AU。

再下一层：N/4 + N/4 + N/4 + N/4 = N个AU。

Summary

  • There is no magic. Just count.
  • 一个比较规范的方法见disc07的andwelcome()：
    • 【1】求Tree Height (number of layers)，如二叉树的话就是$logN$
    • 【2】求branching factor（分叉系数/ nodes per layer），如二叉树是$2^N$
    • 【3】求每个node的operations (work per node)，如二叉树是$N/2^i$
    • 最后乘起来：$\sum_{i=0}^{logN}\space·\space2^i\space·\space(\frac{N}{2^i}) = n\log{N}$