Lec2-Algorithm Analysis

数据结构预习ing....

Lec2-Algorithm Analysis

1. Why Do We Analyze Algorithms?

English Explanation:

Analyzing algorithms helps us to:

Understand efficiency: Evaluate how well an algorithm performs in terms of time and space resources.
Predict scalability: Determine how the algorithm behaves as the input size grows, especially for large data sets.
Choose the best solution: Compare multiple algorithms to select the one that meets performance and resource requirements.
Optimize code: Identify bottlenecks or inefficiencies and improve the implementation.

2. How Do We Measure the Efficiency of an Algorithm?

We typically measure an algorithm's efficiency by analyzing its time complexity and space complexity, which describe the resources required in relation to the input size $ n $.

Options Analysis

A. Time it on my computer.

English: This method measures execution time on a specific hardware and software environment. It is not reliable for theoretical analysis because it depends on external factors like CPU speed and system load.
中文： 这种方法测量的是在特定硬件和软件环境下的执行时间。由于依赖于 CPU 速度和系统负载等外部因素，不适合作为理论分析方法。

B. Compare its time to that of another algorithm that has already been analyzed.

English: Comparing algorithms directly can provide insights, but it doesn't offer an independent, generalized measure of efficiency.
中文： 直接比较算法可以提供一定的参考，但无法提供独立且通用的效率指标。

C. Count how many instructions it will execute for an arbitrary input data set.

English: This method is the foundation of time complexity analysis, as it focuses on the number of basic operations as a function of the input size. This approach is independent of hardware and provides a theoretical performance measure.
中文： 这种方法是 时间复杂度分析 的基础，关注基本操作次数与输入规模的关系。它不依赖硬件，提供了理论上的性能指标。

Correct Answer: C

简单计算模型（Simple Model of Computation）

模型特点：

顺序执行：
- 指令按照先后顺序逐条执行，不存在并行或多线程执行的情况。
标准指令集：
- 仅包含基本操作，例如加法、乘法、比较和赋值等常见指令。
- 不包含复杂操作，如矩阵求逆或排序。
指令执行时间：
- 每条基本指令耗时固定，具体为1个时间单位：
  - 加法（Addition）：1个时间单位。
  - 乘法（Multiplication）：1个时间单位。
  - 比较（Comparison）：1个时间单位。
  - 赋值（Assignment）：1个时间单位。
数据限制：
- 固定大小的整数：
  - 假设整数为固定大小，例如32位整数，意味着整数有最大表示范围。
- 不支持浮点数或动态大小的整型操作。
内存假设：
- 无限内存：
  - 假设可用内存无限大，不会因为空间不足限制操作的执行。

分析内容（What to Analyze）

需要分析的内容：

运行时间（Running Time Required）
- 程序运行所需的时间，通常与算法的效率直接相关。
- 使用时间复杂度（如 $O(n)$）来衡量。
内存或磁盘空间（Memory or Disk Space Required）
- 程序运行和存储数据结构所需的空间资源。
- 使用空间复杂度（如 $O(n^2)$）来衡量。

主要影响因素：

算法（The Algorithm Used）
- 所选算法的性质会直接影响运行时间和空间使用，例如快速排序和冒泡排序的效率不同。
输入数据（The Input to the Algorithm）
- 输入的规模（如数据量 $n$ 的大小）和特性（如数据是否已排序）会对运行效率产生显著影响。
- 通常需要分析最优情况、最差情况和平均情况。

不需要分析的内容：

编程语言（Programming Language）
- 编程语言的选择对算法的核心分析无影响，只与实际实现性能有关。
编译器（Compiler）
- 编译器优化虽然可以提高实际执行效率，但不改变算法的理论性能指标。

算法复杂度定义

1. 大 O 表示法：

定义：
$ T(N) = O(f(N)) $，如果存在正常数 $ c $ 和 $ n_0 $，使得当 $ N n_0 $ 时：
$ T(N) c f(N) $
解释：

上界：描述算法的运行时间或资源使用量的上界。
表示 $ T(N) $ 的增长速度不会超过 $ f(N) $ 的增长速度（在某个点之后）。
常用于表示算法的最坏情况时间复杂度。

2. 大 Ω 表示法：

定义：
$ T(N) = (g(N)) $，如果存在正常数 $ c $ 和 $ n_0 $，使得当 $ N n_0 $ 时：
$ T(N) c g(N) $
解释：

下界：描述算法的运行时间或资源使用量的下界。
表示 $ T(N) $ 的增长速度不会低于 $ g(N) $ 的增长速度（在某个点之后）。
常用于表示算法的最佳情况时间复杂度。

3. 大 Θ 表示法：

定义：
$ T(N) = (h(N)) $，当且仅当：

$ T(N) = O(h(N)) $，且
$ T(N) = (h(N)) $。

解释：

表示 $ T(N) $ 的增长速度与 $ h(N) $ 的增长速度是相同的（在某个点之后）。
用于描述算法的平均情况时间复杂度或精确增长率。

4. 小 o 表示法：

定义：
$ T(N) = o(p(N)) $，如果对于任意正常数 $ c $，存在一个 $ n_0 $，使得当 $ N > n_0 $ 时：
$ T(N) < c p(N) $
解释：

表示 $ T(N) $ 的增长速度比 $ p(N) $ 的增长速度更慢（严格小于）。
常用于描述更严格的上界，即 $ T(N) $ 是 $ p(N) $ 的渐进弱上界。

总结表格：

符号	描述	数学定义
$ O $	上界（最坏情况）	$ T(N) c f(N), , N n_0 $
$ $	下界（最佳情况）	$ T(N) c g(N), , N n_0 $
$ $	上下界相同（平均情况）	$ c_1 h(N) T(N) c_2 h(N), , N n_0 $
$ o $	严格上界（渐进弱上界）	$ T(N) < c p(N), , N > n_0 $

算法复杂度简化规则（Simplifying Rules）

规则 1：关于加法和乘法的复杂度规则

加法规则：
如果 $ T_1(N) = O(f(N)) $ 且 $ T_2(N) = O(g(N)) $，那么：$ T_1(N) + T_2(N) = O(f(N) + g(N)) $
解释：
- 算法的总体复杂度为两个子部分复杂度的和。
乘法规则：
如果 $ T_1(N) = O(f(N)) $ 且 $ T_2(N) = O(g(N)) $，那么：$ T_1(N) T_2(N) = O(f(N) g(N)) $
解释：
- 算法复杂度在子部分复杂度相乘时按对应增长率计算。

规则 2：关于多项式的复杂度规则

如果 $ T(N) $ 是一个 $ k $ 次多项式（例如 $ T(N) = a_kN^k + a_{k-1}N^{k-1} + + a_0 $），那么：$ T(N) = (N^k) $
解释：
- 多项式的复杂度由最高次项决定，忽略低次项和常数系数。

规则 3：对数的复杂度规则

对于任意常数 $ k $，有：$ ^k N = O(N) $
解释：
- 对数函数的增长速度远小于线性函数（$ N $），因此是其渐进上界。

规则 4：传递性规则（Transitivity）

如果 $ T(N) = O(g(N)) $ 且 $ g(N) = O(h(N)) $，那么：$ T(N) = O(h(N)) $
解释：
- 渐进上界具有传递性，可将复杂度逐层转化。

规则 5：忽略常数规则（Ignore Constants）

如果 $ T(N) = O(k g(N)) $，其中 $ k > 0 $ 为常数，那么：
$ T(N) = O(g(N)) $
解释：
- 常数因子对渐进复杂度无影响，忽略即可。

表格：

规则编号	规则内容	解释
规则 1	$ T_1(N) + T_2(N) = O(f(N) + g(N)) $	总复杂度是两个子部分复杂度的和
	$ T_1(N) T_2(N) = O(f(N) g(N)) $	子部分复杂度相乘，取对应增长率
规则 2	$ T(N) = (N^k) $（$ T(N) $ 是 $ k $ 次多项式）	高次项主导复杂度
规则 3	$ ^k N = O(N) $	对数增长速度低于线性
规则 4	如果 $ T(N) = O(g(N)) $ 且 $ g(N) = O(h(N)) $，则 $ T(N) = O(h(N)) $	渐进复杂度具有传递性
规则 5	$ T(N) = O(k g(N)) $，常数 $ k $ 可忽略，即 $ T(N) = O(g(N)) $	常数因子不影响渐进复杂度

如何进行算法分析

1. 渐进算法分析（Asymptotic Algorithm Analysis）

定义：
渐进算法分析通过输入规模变大时的增长率来评估算法的效率。
目的：
- 不关心具体的常数因子和小规模输入的性能。
- 注重输入规模趋于无穷大时，算法的性能趋势。

2. 常见的分析维度

分析类型	描述	作用
最优情况（Best-case）	输入情况下算法的最快运行时间，即所有可能输入中开销最小的情况。	用于评估在理想情况下算法的效率，但不代表实际保证。
平均情况（Average-case）	所有可能输入的平均运行时间，通常需要概率模型来计算。	更贴近实际性能评估，但可能需要更多假设条件。
最坏情况（Worst-case）	输入情况下算法的最慢运行时间，即所有可能输入中开销最大的情况。	提供对任何输入都成立的性能保证，重要于安全性和稳定性评估。

算法成本分析

Q1: 查找特定值 $ K $ 的成本

对于查找特定值 $ K $ 的情况，顺序查找算法（Sequential Search）在不同输入情况下的成本可能会有所不同。

最优情况（Best Case）：
如果第一个整数就是 $ K $，则只需要检查一个值。此时的时间复杂度为常数 $ O(1) $，即只进行一次比较。
1
2
3
4
5
6
int sumit(int v[], int num) {
sum = 0;
for (int i = 0; i < num; i++)
sum += v[i];
return sum;
}
最坏情况（Worst Case）：
如果只有最后一个整数是 $ K $，则需要检查所有 $ n $ 个元素。此时的时间复杂度为 $ O(n) $，即需要进行 $ n $ 次比较。
平均情况（Average Case）：
如果顺序查找在不同输入下多次执行，则平均需要检查 $ $ 个元素。因此，平均情况下的时间复杂度为 $ O(n) $，因为对于大规模数据，常数项可以忽略。

Q2: 查找最大值的成本

查找数组中最大值的成本分析：

时间复杂度：
在顺序查找最大值的过程中，我们需要逐个比较每个元素。假设数组的大小为 $ n $，则时间复杂度为 $ O(n) $，即需要检查 $ n $ 个元素。

假设算法中常数因子为 $ c $，则计算最大值的成本可以表示为：$ c n T(num) = (c_2 + c_3) n + (c_1 + c_4) $ 其中，$ T(num) = O(n) $ 表示时间复杂度是线性的。

嵌套循环的成本分析

双重循环： 假设我们有一个双重循环，外层循环从 $ 1 $ 到 $ n $，内层循环从 $ 1 $ 到 $ n $，每次增加一个计数器的操作：
1
2
3
4
5
6
int sum(int n) {
int sum = 0;
for (i = 1; i <= n; i++) // 外层循环：n次
for (j = 1; j <= n; j++) // 内层循环：n次
sum++;
}
这段代码的时间复杂度为 $ O(n^2) $，因为有 $ n $ 次外层循环，每次外层循环执行 $ n $ 次内层循环。
对数复杂度： 假设我们使用了对数阶的外层循环（例如，循环变量是指数递增的）：
1
2
3
4
sum = 0;
for (k = 1; k <= n; k *= 2) // 外层循环：log(n)次
for (j = 1; j <= n; j++) // 内层循环：n次
sum++;
外层循环执行的次数是 $ n $（因为 $ k $ 是以 2 为基数增长的），内层循环执行 $ n $ 次，因此总的时间复杂度为 $ O(n n) $。

总结：
这种类型的嵌套循环的时间复杂度是 $ (n n) $，因为外层循环执行 $ n $ 次，内层循环执行 $ n $ 次。

Q3:分析第一个循环代码

代码如下：

sum = 0;
for (k = 1; k <= n; k *= 2)     // 进行 log(n) 次
  for (j = 1; j <= k; j++)       // 每次进行 k 次
    sum++;

外层循环： 外层循环的变量 $ k $ 从 1 开始，每次翻倍，直到 $ k n $ 时停止。这个循环的次数为 $ n $（以 2 为底的对数）。
内层循环： 每次内层循环执行 $ k $ 次，其中 $ k $ 是外层循环的当前值。因此，内层循环的执行次数随着 $ k $ 的增大而增大。

计算总的执行次数：

总的执行次数等于内外循环的总次数之积，即： $ T(n) = _{i=0}^{n} 2^i = 2^{n + 1} - 1 = 2n - 1 $ 因此，时间复杂度为： $ T(n) = (n) $

结论：

该算法的总时间复杂度是 $ (n) $，因为 $ 2n - 1 $ 与 $ n $ 是同阶的，常数项可以忽略。

Q4:分析带有随机生成和排序的代码

代码如下：

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) 
        A[j] = random(n);         // 每次赋值时都调用 random
    sort(A, n);                    // 排序操作
}

外层循环： 外层循环运行 $ n $ 次。
内层循环： 内层循环也运行 $ n $ 次。每次赋值都调用 random(n)，假设 random(n) 的时间复杂度是 $ O(1) $（即每次生成一个随机数的时间是常数）。
排序操作： 排序操作 sort(A, n) 使用一个复杂度为 $ O(n n) $ 的排序算法。

计算总的执行次数：

内层操作： 每次内层操作执行 $ O(n) $ 次。
排序操作： 每次排序操作需要 $ O(n n) $ 时间。

所以，整个代码的时间复杂度是： $ T(n) = n ( O(n) + O(n n) ) $ $ T(n) = O(n^2) + O(n^2 n) $

因此，时间复杂度是： $ T(n) = (n^2 n) $

结论：

该代码的总时间复杂度是 $ (n^2 n) $，由于排序操作的复杂度较高，主导了整体的时间复杂度。

3. 分析含有双重循环的代码

代码如下：

sum = 0;
for (i = 0; i < n; i++) 
    for (j = 0; A[j] != i; j++)   // A[j] 与 i 比较，直到相等
        sum++;

外层循环： 外层循环运行 $ n $ 次，从 $ i = 0 $ 到 $ i = n-1 $。
内层循环： 内层循环对于每个 $ i $，都会从 $ j = 0 $ 开始遍历，直到 $ A[j] = i $ 为止。假设 $ A[] $ 是一个包含 $ 0 $ 到 $ n-1 $ 的随机排列的数组，那么对于每个 $ i $，内层循环的执行次数大约为 $ n-i $，因此内层循环的执行次数是依赖于 $ i $ 的。

计算总的执行次数：

总的执行次数是： $ T(n) = {i=0}^{n-1} (n - i) = {i=0}^{n-1} i = $ 因此，时间复杂度为： $ T(n) = (n^2) $

结论：

该代码的总时间复杂度是 $ (n^2) $，因为内层循环的执行次数随着 $ i $ 的增加逐渐减少，但总的执行次数依然呈现出平方增长的趋势。

一些技巧：

1. while 循环

while 循环的时间复杂度分析与 for 循环类似。关键是确定循环体的执行次数。如果 while 循环的条件在每次迭代时都能按固定的步长减少，则时间复杂度是 O(n)，如果是指数级减少，则复杂度可能是 O(log n)。

2. If-then-else 语句

在分析 if-then-else 语句时，时间复杂度是取 then 和 else 两个分支中最大成本的那一个。这是因为在执行时，只有一个分支会被执行。因此，复杂度为： $ T() = (T_{}, T_{}) $

3. Switch 语句

对于 switch 语句，最昂贵的分支决定了整体的时间复杂度。也就是说，时间复杂度是取所有分支中的最大值。

4. 子程序调用

子程序调用的时间复杂度是该子程序的复杂度。调用的代价需要加到总时间复杂度中。

5. 递归子程序

递归算法的时间复杂度通常通过递归关系来表示。通过求解递归关系可以得到时间复杂度的闭式解。一个典型的递归算法例子如下：

string t(int n){
   if (n == 1) return "(1) ";
   else return "(" + n + t(n - 1) + ") ";
}

递归关系：

当 $ n = 1 $ 时，返回的是一个常数值 (1)。
对于 $ n > 1 $，递归调用 t(n-1)，然后加上当前的 n 和括号。

递归关系为： $ T(n) = T(n - 1) + c $ 其中，$ c $ 是一个常数，表示每次递归调用时进行的字符串连接操作。

递归展开： $ T(n) = T(n - 1) + c = (T(n - 2) + c) + c = ... = T(1) + (n - 1) * c $

因此，时间复杂度为： $ T(n) = c * (n - 1) + c_1 = (n) $ 最终得出该递归函数的时间复杂度是 $ (n) $。

6. 多个参数的情况

考虑一个包含 $ P $ 像素的图片，其中每个像素有 $ C $ 种颜色。要求根据像素的数量对颜色进行排序。步骤如下：

初始化颜色计数：对每种颜色的计数器初始化为 0，时间复杂度为 $ (C) $。
遍历所有像素并增加对应颜色的计数，时间复杂度为 $ (P) $。
对颜色计数数组进行排序，时间复杂度为 $ (C C) $（假设使用高效的排序算法，如归并排序或堆排序）。

总的时间复杂度是： $ T = (C) + (P) + (C C) = (P + C C) $

上下界分析

1. 算法时间复杂度分析（T(n) = c1n² + c2n）

假设算法的时间复杂度在平均情况下为 $ T(n) = c_1n^2 + c_2n $，其中 $ c_1, c_2 > 0 $，我们可以分析其渐进复杂度。

上界分析：
我们需要找到一个常数 $ c $ 使得对所有 $ n > 1 $，都满足 $ T(n) cn^2 $。
- $ T(n) = c_1n^2 + c_2n $
- 对于 $ n > 1 $，我们有：$ c_1n^2 + c_2n (c_1 + c_2)n^2 $
  - 这里，我们可以取 $ c = c_1 + c_2 $，则对于所有 $ n > 1 $，有：$ T(n) (c_1 + c_2)n^2 = cn^2 $ 因此，$ T(n) = O(n^2) $。
下界分析：
我们需要找到一个常数 $ c $ 使得对所有 $ n > 1 $，都满足 $ T(n) c_1n^2 $。
- 对于 $ n > 1 $，我们有：$ c_1n^2 + c_2n c_1n^2 $
  - 所以，$ T(n) c_1n^2 $，因此 $ T(n) = (n^2) $。
渐进紧界（Θ）分析：
由于我们得到了 $ T(n) = O(n^2) $ 和 $ T(n) = (n^2) $，可以得出：$ T(n) = (n^2) $ 这意味着该算法在平均情况下的时间复杂度是 $ (n^2) $，即它的增长率是 $ n^2 $。