Post

chap1 基本概念

Posted Updated
By floyd white
22 min read
chap1 基本概念
  1. 为什么在时间复杂度估计中，nlogn>n？比如当n<1时不是前者不是小于后者吗？

答：在算法的时间复杂度分析中，我们通常关注的是当输入规模 n 变得非常大时（n 趋向于无穷大）函数的增长行为，而不是小数值的情况。

例1.6

![[截屏2025-03-09 12.40.25.png|200]]
对于这个算法：

情况 1：当 n是素数时

  • 需要完整遍历循环：从 j=2 到 j=s，共执行 ⌊n⌋−1 次循环。

  • 时间复杂度：此时算法是 O(n) 的，因为运行时间与 n​ 成正比。

情况 2：当 n 是偶数时

  • 立即终止循环：第一次循环 j=2 就能发现 n 是偶数，直接返回 false。

  • 时间复杂度：此时算法是 O(1) 的，因为只需要一次判断。

为什么算法无法用 Θ 表示？

  1. Θ 符号的含义：

    • 若算法的时间复杂度是 Θ(f(n))，则必须同时满足：

      • 上界：存在常数 c1​，使得对足够大的 n，运行时间 T(n)≤c1⋅f(n)（即 O(f(n))）。

      • 下界：存在常数 c2​，使得对足够大的 n，运行时间 T(n)≥c2⋅f(n)（即 Ω(f(n))）。

  2. 矛盾点：

    • 对于无限多的素数（如 n=3,5,7,11,…），运行时间是 Ω(n)（因为必须检查所有可能的因数）。

    • 对于无限多的偶数（如 n=4,6,8,10,…），运行时间是 O(1)。

    • 没有统一的 f(n)f(n)：
      如果强行认为它是 Θ(n)，那么对于偶数 n，运行时间 O(1)不满足 Ω(n)的下界；
      如果认为它是 Θ(1)，那么对于素数 n，运行时间 O(n) 不满足 O(1) 的上界。

    • 结论：算法的时间复杂度在不同输入下差异太大，无法用单一的 Θ(f(n))描述。

1.8 复杂性类与o符号

1. 复杂性类（Complexity Classes）
  • 定义：将增长率相同的函数归为同一类，分类依据是 $\Theta$ 符号（紧确界）。
    • 等价关系：若 $f(n) = \Theta(g(n))$，则 $f$ 和 $g$ 属于同一复杂性类。
    • 示例：所有二次多项式（如 $3n^2 + 5n$、$n^2 - 100$）均属于 $\Theta(n^2)$ 类。
2. $o$ 符号（小o）
  • 定义：若 $f(n) = o(g(n))$，则当 $n \to \infty$ 时，$f(n)$ 的增长速度严格低于 $g(n)$（即 $f(n)$ 可以忽略不计）。
    • 数学条件：对任意小的常数 $c > 0$，存在 $n_0$，使得当 $n \geq n_0$ 时，$f(n) < c \cdot g(n)$。
    • 极限定义：若 $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$，则 $f(n) = o(g(n))$。
    • 示例：$n \log n = o(n^2)$，因为 $\frac{n \log n}{n^2} = \frac{\log n}{n} \to 0$。

关键区别：$O$ vs $\Theta$ vs $o$

| 符号 | 含义 | 示例（假设 $g(n) = n^2$） |
|———-|————————|———————————–|
| $O$ | 上界（可能同阶） | $3n^2 = O(n^2)$，$n = O(n^2)$ |
| $\Theta$ | 紧确界（严格同阶） | $3n^2 = \Theta(n^2)$，$n^2 \neq \Theta(n)$ |
| $o$ | 严格上界（增速更慢） | $n \log n = o(n^2)$，$n \neq o(n)$ |

复杂性类层次结构

以下是从低到高的增长速率排序（用 $<$ 表示 $o$ 关系）：
$1 < \log \log n < \log n < \sqrt{n} < n^{3/4} < n < n \log n < n^2 < 2^n < n! < 2^{n^2}$
含义：左侧的函数增速极慢，右侧的函数增速极快。例如：

  • $\log n$ vs $n$：对数函数 $\log n$ 的增速远慢于线性函数 $n$。
  • $2^n$ vs $n!$：指数函数 $2^n$ 的增速远慢于阶乘函数 $n!$。

为什么需要这些概念？

  1. 算法分析：
    • 若某算法的时间复杂度为 $\Theta(n^2)$，说明其运行时间严格与 $n^2$ 成正比。
    • 若为 $o(n^2)$，则其增速比所有 $n^2$ 的常数倍更慢（例如 $n \log n$）。
  2. 问题分类：
    • 复杂性类帮助区分问题的难度。例如，能在 $O(n)$ 时间内解决的问题比需要 $O(2^n)$ 的问题“容易”。

通俗类比

  • $\Theta$ 符号：
    就像两辆赛车以完全相同的速度行驶（例如 $3n^2$ 和 $5n^2$），它们属于同一“速度等级”。

  • $o$ 符号：
    就像一辆自行车（$n \log n$）和一辆高铁（$n^2$），自行车的速度永远无法追上高铁，且差距会越来越大。

  • 层次结构：
    类似于动物体型大小的排序：蚂蚁（$\log n$） < 猫（$n$） < 大象（$n^2$） < 蓝鲸（$2^n$）。

1.9 空间复杂性

空间复杂度与时间复杂度

  • 算法的空间复杂性不可能超过运行时间的复杂性，因为写入每一个内存单元都至少需要一定的时间；
  • 这样，如果用 T(n)和 S(n)分别代表算法的时间复杂性和空间复杂 性，则有 S(n) =O(T(n))。

例子

例 1.18

在合并两个已排序序列的算法 MERGE 中，需要大小为 $n$（和输入大小相同，$n$ 为 $A[p \cdots r]$ 的大小）的辅助存储器，因此空间复杂性是 $\Theta(n)$。

例 1.19

在试图估计算法 BOTTOMUPSORT 所需的空间大小时，起初会认为这个问题比较复杂。尽管如此，不难看出所需空间不超过输入数组的大小 $n$，这是由于我们可以留出大小为 $n$ 的一个数组 $B[1 \cdots n]$，作为算法 MERGE 用来完成合并过程的辅助存储器。由此可以得出，算法 BOTTOMUPSORT 的空间复杂性为 $\Theta(n)$。

例 1.20

本例中，我们“设计”一个使用 $\Theta(\log n)$ 空间的算法。首先修改算法 BINARYSEARCH，搜索结束后，输出一个在数组 $A$ 中和 $x$ 比较过的元素的已排序列表。这意味着我们在每次循环中测试 $x$ 不是 $A[\text{mid}]$ 后，必须用一个辅助数组 $B$ 来存储 $A[\text{mid}]$，然后再对 $B$ 进行排序。由于比较次数最多是 $\lfloor \log n \rfloor + 1$，因此容易得出 $B$ 的大小最多是 $O(\log n)$。

例 1.21

输出给定的 $n$ 个字符的所有排列只需要 $\Theta(n)$ 空间。如果需要保留这些排列用于后续计算，则至少需要 $n \times n! = \Theta((n+1)!)$ 空间。

疑问

空间复杂度会算上输入规模n吗？比如排序算法所输入的n元数组

答：空间复杂度关注的是算法额外申请的辅助空间，如临时变量、递归栈、合并操作的缓冲区等。
比如，排序算法中，输入数组占用的空间是O(n)，但如果排序算法只需要常数级别的额外空间（如O(1)），那么它的空间复杂度就是O(1)，而不是O(n)。

1.10 最优算法

一般来说，如果可以证明任意一个求解问题Q的算法必定是$\Omega(f(n))$ 的，那么我们把在$\Omega(f(n))$ 时间内求解问题Q的任何算法都称为问题Q的最优算法。

1.11 如何估计算法的运行时间

当然可以把所有元运算加起来得到一个精确的界限，但无疑这种方法是不可取的，因为它十分庥烦且常常是不可能实现的。

在许多算法中有一些公认的技术可以通过直接分析给出一个紧密界，下面通过一些例子来讨论这些技术。

1.11.1 计算迭代次数

核心概念
1. 迭代次数与运行时间的关系

算法的运行时间通常与 循环结构的执行次数 成正比（如 while、for 循环）。例如：

  • 搜索算法：遍历元素的次数直接影响时间。
  • 排序算法：比较和交换操作的次数决定效率。
  • 矩阵乘法：嵌套循环的迭代次数主导耗时。
2. 如何计算迭代次数？
  • 关键步骤：找到算法中 执行最频繁的语句（如循环体内的操作）。
  • 假设：每条语句的执行时间为常数，总时间可近似为迭代次数的函数，并用 $O(\cdot)$ 或 $\Theta(\cdot)$ 表示。
3. 简单循环的数学表示

若循环的迭代变量 每次递增 1（称为“简单循环”），可直接转化为 求和式。
示例代码：

1
2
3
4

count ← 0
for i ← low to high:
    count ← count + 1
end for

对应的求和式：
\(\text{count} = \sum_{i=low}^{high} 1\)

  • 含义：循环从 low 到 high 共执行 $(\text{high} - \text{low} + 1)$ 次。
嵌套循环与双重求和
例 1.22：双重循环的迭代次数

假设 $n$ 是完全平方数（即 $\sqrt{n}$ 是整数），算法 COUNT1 对每个完全平方数 $j$（$1 \leq j \leq \sqrt{n}$），计算 $1$ 到 $j$ 的和 $\sum_{i=1}^{j} i$。

  • 外层循环：遍历所有完全平方数 $j$（共 $\sqrt{n}$ 次）。
  • 内层循环：对每个 $j$，计算 $1$ 到 $j$ 的和（需 $j$ 次迭代）。

总迭代次数：
外层循环次数 $\times$ 内层循环次数，转化为双重求和：
\(\sum_{j=1}^{\sqrt{n}} \sum_{i=1}^{j} 1\)
简化后：
\(\sum_{j=1}^{\sqrt{n}} j = \frac{\sqrt{n}(\sqrt{n} + 1)}{2} = \Theta(n)\)

关键分析步骤
  1. 识别循环类型：
    • 简单循环（迭代变量线性递增） → 直接求和。
    • 嵌套循环 → 分层求和（外循环与内循环相乘）。
  2. ==转化为数学表达式==$\sum$：
    • 外层循环变量作为求和指标。
    • 内层循环次数作为求和上限。
  3. 时间复杂度估算：
    • 单层循环：$O(n)$、$\Theta(n)$。
    • 双重循环：$O(n^2)$、$\Theta(n^2)$。
简单循环与非简单循环

简单循环：循环变量如i、j是+1递增的，而不简单的循环的变量是每次循环*2或其他操作。

如何解决含有非简单循环的时间分析？

方法是：设置一个新的达到简单性要求的迭代变量，以便将其包含于和式$\sum$中。

例：
![[截屏2025-03-09 16.35.59.png|500]]

1.1.2 计算基本运算的频度

基本运算的定义与重要性

在算法分析中，精确计算所有操作的运行时间通常非常麻烦甚至不可能。因此，我们采用一种简化方法：识别算法中的”基本运算”。

定义1.6：如果算法中某个元运算具有最高频度，而所有其他元运算频度均在它的频度的常数倍内，则称这个元运算为基本运算。

MERGE算法的例子

文中以归并排序(MERGE)算法为例说明基本运算的概念：

  1. 在MERGE算法中，元素赋值操作是基本运算
  2. 对于大小为n的两个数组合并，需要的元素赋值次数正好是2n次
  3. 因此MERGE算法的运行时间是O(n)
  4. 元素比较运算通常不是基本运算，因为整个算法执行过程中可能只执行一次比较操作
  5. 但在特殊情况下，如合并大小相同的两个数组(⌊n/2⌋和⌈n/2⌉)时，元素比较可以成为基本运算
确定基本运算的方法

确定算法的基本运算是分析算法运行时间的关键步骤。文中列出了不同类型算法的基本运算候选：

  1. 搜索和排序算法：元素比较通常可选为基本运算
  2. 遍历链表：设置或更新指针的运算可选为基本运算
  3. 图的遍历：访问节点的动作和对被访问节点的计数可选为基本运算
分析方法

分析算法运行时间的方法包括两部分：

  1. 确定一种基本运算
  2. 应用递推关系式来找出这种运算执行的阶数

1.12 最坏情况与平均情况分析

基本概念

  1. 输入无关的算法：
    • 示例：两个 $n \times n$ 矩阵相加。
    • 特点：无论输入矩阵的具体数值如何，算法执行的操作次数（如加法次数）始终固定为 $n^2$。
    • 结论：时间复杂度仅由输入大小 $n$ 决定，与输入数据的形式无关。
  2. 输入相关的算法：
    • 示例：插入排序（INSERTIONSORT）。
    • 特点：算法的运行时间受输入数据的初始顺序显著影响。
      • 最坏情况：输入数组为降序排列，需执行最多比较次数（$\frac{n(n-1)}{2}$）。
      • 最佳情况：输入数组已升序排列，仅需 $n-1$ 次比较。
      • 平均情况：随机排列的输入，比较次数介于上述两者之间。
    • 结论：时间复杂度不仅是 $n$ 的函数，还与输入数据的分布有关。
  3. 输入无关的排序算法：
    • 示例：选择排序（SELECTIONSORT）。
    • 特点：无论输入顺序如何，比较次数固定为 $\frac{n(n-1)}{2}$。
    • 结论：某些算法的运行时间完全由输入大小决定，与数据形式无关。

三种时间复杂度的分析方法

  1. 最坏情况分析（Worst-Case Analysis）：
    • 定义：针对所有可能输入中运行时间最长的情况进行分析。
    • 意义：提供算法性能的上界保证，确保算法在任何输入下不会超过此时间。
    • 示例：插入排序的最坏时间复杂度为 $O(n^2)$。
    • 用$\Theta(g(n))$描述最坏情况下算法的运行时间，比用$\Omega$和$O$都好。
  2. 平均情况分析（Average-Case Analysis）：
    • 定义：假设输入数据服从某种概率分布（如均匀随机），计算期望运行时间。
    • 意义：反映算法在典型输入下的性能，但依赖对输入分布的合理假设。
    • 示例：快速排序的平均时间复杂度为 $O(n \log n)$。
  3. 最佳情况分析（Best-Case Analysis）：
    • 定义：针对所有可能输入中运行时间最短的情况进行分析。
    • 意义：通常不具实际价值，因为算法设计需关注最坏或平均性能，而非理想化场景。
    • 示例：插入排序的最佳时间复杂度为 $O(n)$，但此情况极少出现。

1）最坏情况分析（存疑）

下面这个问题我没明白：什么叫”最坏情况下界“？既然是最坏情况那不就应该是算法所耗时间最长吗？为什么还是下界？
![[Pasted image 20250309223634.png|500]]

解答：

如下图，最坏情况的定义是 在同样的输入大小下（比如都输入长度为k的数组），对于同一个算法InsertionSort、同样的输入量k，这些输入的排列顺序会对算法运行时间产生影响。但我还是没明白最坏情况下界指的是什么？
![[截屏2025-03-09 22.39.58.png|500]]

2）平均情况分析

重点是假设“每个输入情况的概率分布”

![[截屏2025-03-09 22.49.51.png500]]

1.13 平摊分析

1、与平均情况分析的区别

  1. 不需要假设输入的概率分布
  2. 不需要计算同样大小的所有实例才能得到平均值

2、情境引入

考虑这样一个算法，其中的一种运算反复执行时具有这样的特性：它的运行时间始终变动。如果这一运算在大多数时候运行得很快，只是偶尔要花费大量时间，又假定求确界虽然可能，但是非常困难，那么这就预示要使用平摊分析了。

3、例子

见P31：例1.33～1.34

平摊分析考虑的是一系列操作的总成本，然后平均到每个操作上。

1.14 输入大小和问题实例

1）概念

a.实例

比如某个具体的数组A={1,2,3,4,5,6}

b.输入大小

不一定是数量，也可以是输入矩阵的维度等等

2）FIRST vs. SECOND算法的比较

这个例子强调了在分析算法时正确理解输入大小的重要性 - 有时候我们需要考虑输入的比特表示，而不仅仅是它的数值大小。

Algorithm Design, Basics
basics
This post is licensed under CC BY 4.0 by the author.