离散习题讲解（8）

她来听我的演唱会......

问题：

描述一个算法，输入为一个包含 $ n $ 个整数的列表，找出该列表中负整数的数量。

解答与解释：

为了计算列表中负整数的个数，我们需要遍历列表中的每个整数，并对负整数进行计数。以下是算法的步骤：

算法步骤：

1. 输入： 一个包含 $ n $ 个整数的列表 $ a_1, a_2, , a_n $。
2. 初始化： 设置一个变量 $ k $ 用于存储负整数的数量，初始值为 0。
3. 遍历列表： 对于列表中的每个元素 $ a_i $：
   • 如果 $ a_i $ 小于 0（即负数），则将 $ k $ 增加 1。
4. 返回结果： 最后返回 $ k $，它表示负整数的数量。

算法描述（伪代码）：

procedure negatives(a1, a2, ..., an: integers)
    k := 0              // 初始化计数器
    for i := 1 to n do  // 遍历列表中的每个元素
        if ai < 0 then  // 如果 ai 是负数
            k := k + 1  // 增加计数器
    return k            // 返回负整数的数量

解释：

1. 初始化： 我们使用一个计数器 $ k $ 来追踪负整数的数量。最开始，$ k = 0 $。
2. 遍历列表： 使用循环从 $ i = 1 $ 到 $ i = n $ 依次访问列表中的每个元素 $ a_i $。对于每个 $ a_i $，我们检查它是否小于 0。如果是负数，则 $ k $ 增加 1。
3. 返回结果： 当循环结束后，计数器 $ k $ 就包含了列表中负整数的个数。

时间复杂度分析：

• 时间复杂度： 该算法需要遍历列表中的每个元素一次，因此时间复杂度是 $ O(n) $，其中 $ n $ 是列表的长度。
• 空间复杂度： 该算法只使用了一个额外的变量 $ k $ 来存储负整数的数量，因此空间复杂度是 $ O(1) $。

示例：

假设列表是 $ a = [3, -1, 4, -2, -5] $。

• 初始化 $ k = 0 $。
• 遍历每个元素：
  • $ 3 $ 不是负数，跳过。
  • $ -1 $ 是负数，$ k = k + 1 = 1 $。
  • $ 4 $ 不是负数，跳过。
  • $ -2 $ 是负数，$ k = k + 1 = 2 $。
  • $ -5 $ 是负数，$ k = k + 1 = 3 $。
• 最终返回 $ k = 3 $，表示列表中有 3 个负整数。

结论：

该算法通过遍历列表并计数负整数的数量来解决问题，时间复杂度为 $ O(n) $，空间复杂度为 $ O(1) $。

问题：

列出在序列 $ 1, 3, 4, 5, 6, 8, 9, 11 $ 中搜索数字 9 的所有步骤：

1. 线性搜索 (Linear Search)
   
2. 二分查找 (Binary Search)

解答与解释：

给定序列 $ 1, 3, 4, 5, 6, 8, 9, 11 $，我们需要使用线性搜索和二分查找方法来搜索数字 9。

a) 线性搜索：

线性搜索是逐个检查列表中的每个元素，直到找到目标元素。其过程是顺序的。

1. 初始化： 从序列的第一个元素开始，设 $ i = 1 $（索引从 1 开始）表示当前检查的元素位置。
2. 逐步检查：
   • $ i = 1 $，检查元素 $ 1 $，目标是 9，未找到。
   • $ i = 2 $，检查元素 $ 3 $，目标是 9，未找到。
   • $ i = 3 $，检查元素 $ 4 $，目标是 9，未找到。
   • $ i = 4 $，检查元素 $ 5 $，目标是 9，未找到。
   • $ i = 5 $，检查元素 $ 6 $，目标是 9，未找到。
   • $ i = 6 $，检查元素 $ 8 $，目标是 9，未找到。
   • $ i = 7 $，检查元素 $ 9 $，找到了目标，位置为 7。
3. 结果： 线性搜索返回位置 7，表示数字 9 位于序列的第 7 个位置。

线性搜索步骤：

i := 1, i := 2, i := 3, i := 4, i := 5, i := 6, i := 7
location := 7

b) 二分查找：

二分查找是一种高效的查找方法，前提是序列已排序。它通过不断将搜索区间一分为二来查找目标元素。

1. 初始化： 设定初始的搜索区间为整个序列。令 $ i = 1 $ 和 $ j = 8 $，表示序列的首尾索引。
2. 计算中间位置： 计算中间位置 $ m $，并检查中间元素与目标值的关系。
   • $ m = = = 4 $，此时检查位置 4 对应的元素是 $ 5 $。
   • 由于 $ 5 < 9 $，说明目标值在右半部分，因此更新搜索区间为 $ i = 5 \(，\) j = 8 $。
3. 计算新中间位置：
   • $ m = = 6 $，此时检查位置 6 对应的元素是 $ 8 $。
   • 由于 $ 8 < 9 $，目标值仍在右半部分，因此更新搜索区间为 $ i = 7 \(，\) j = 8 $。
4. 计算新中间位置：
   • $ m = = 7 $，此时检查位置 7 对应的元素是 $ 9 $。
   • 找到了目标元素 9，位置为 7。
5. 结果： 二分查找返回位置 7，表示数字 9 位于序列的第 7 个位置。

二分查找步骤：

i := 1, j := 8
m := 4, i := 5, m := 6, i := 7, m := 7, j := 7
location := 7

总结：

• 线性搜索：逐个检查每个元素，直到找到目标，时间复杂度为 $ O(n) $，其中 $ n $ 是列表的长度。
• 二分查找：通过不断将查找范围缩小一半来查找目标，时间复杂度为 $ O(n) $，前提是列表已经排序。

对于给定的序列 $ 1, 3, 4, 5, 6, 8, 9, 11 $：

• 线性搜索需要检查 7 个元素，最后在第 7 个位置找到目标 9。
• 二分查找通过 3 次比较（中间位置 4、6 和 7）成功找到目标 9，时间复杂度较低。

问题：

找到使得每个函数 $ f(x) $ 满足 $ f(x) = O(x^n) $ 的最小整数 $ n $。

a) $ f(x) = 2x^3 + x^2 x $

b) $ f(x) = 3x^3 + (x)^4 $

c) $ f(x) = $

d) $ f(x) = $

解答与解释：

a) $ f(x) = 2x^3 + x^2 x $

我们需要找到 $ f(x) $ 的增长率。函数由两个部分组成：

• $ 2x^3 $，这是一个多项式函数，增长速率为 $ O(x^3) $。
• $ x^2 x $，这里的对数项增长速度较慢，远低于 $ x^3 $，因此 $ x^2 x $ 的增长速率为 $ O(x^2 x) $，这比 $ x^3 $ 增长得慢。

因此，整个函数的增长速率由最大的项决定，即 $ 2x^3 $。所以 $ f(x) = O(x^3) $。

最小 $ n $： $ n = 3 $

b) $ f(x) = 3x^3 + (x)^4 $

这个函数有两个部分：

• $ 3x^3 $，这部分增长速率为 $ O(x^3) $。
• $ (x)^4 $，这是对数函数，增长比任何多项式都慢，因此它的增长速率是 $ O((x)^4) $。

由于对数项 $ (x)^4 $ 的增长速率远低于 $ x^3 $，所以整体函数的增长速率是由 $ 3x^3 $ 主导的。

最小 $ n $： $ n = 3 $

c) $ f(x) = $

对于这个分式函数，我们考虑分子和分母的增长速率：

• 分子的最大项是 $ x^4 $，所以分子增长速率为 $ O(x^4) $。
• 分母的最大项是 $ x^3 $，所以分母增长速率为 $ O(x^3) $。

因此，整个分式的增长速率为：

$ f(x) = = O(x) $

最小 $ n $： $ n = 1 $

d) $ f(x) = $

对于这个分式函数，我们考虑分子和分母的增长速率：

• 分子的最大项是 $ x^4 $，所以分子增长速率为 $ O(x^4) $。
• 分母的最大项是 $ x^4 $，所以分母增长速率为 $ O(x^4) $。

因此，整个分式的增长速率为：

$ f(x) = = O(1) $

最小 $ n $： $ n = 0 $

总结：

• 1. $ n = 3 $
• 2. $ n = 3 $
• 3. $ n = 1 $
• 4. $ n = 0 $

问题：

给出每个函数的最好的大 $ O $ 估计。

a) $ (n^2 + 8)(n + 1) $

b) $ (n n + n²⁾⁽ⁿ3 + 2) $

c) $ (n! + 2ⁿ⁾⁽ⁿ3 + (n^2 + 1)) $

解答与解释：

a) $ (n^2 + 8)(n + 1) $

首先，展开该表达式：

$ (n^2 + 8)(n + 1) = n^2(n + 1) + 8(n + 1) $ $ = n^3 + n^2 + 8n + 8 $

我们可以看到该表达式中最高的项是 $ n^3 \(，其他项（\) n^2, n, $）都比 $ n^3 $ 增长得慢，因此其增长速率由 $ n^3 $ 主导。

最好的大 $ O $ 估计：
$ O(n^3) $

b) $ (n n + n²⁾⁽ⁿ3 + 2) $

首先，我们展开该表达式：

$ (n n + n²⁾⁽ⁿ3 + 2) = n n n^3 + n n + n^2 n^3 + n^2 $ $ = n^4 n + 2n n + n^5 + 2n^2 $

在这些项中，最具增长速度的是 $ n^5 $，其次是 $ n^4 n $。所以整个表达式的增长速度由 $ n^5 $ 主导。

最好的大 $ O $ 估计：
$ O(n^5) $

c) $ (n! + 2ⁿ⁾⁽ⁿ3 + (n^2 + 1)) $

我们首先分析每一部分：

• $ n! $ 和 $ 2^n $ 是两个增长速度极快的项，尤其是 $ n! $ 的增长速度要比 $ 2^n $ 快得多。因此，$ n! $ 会主导该部分。
• $ n^3 + (n^2 + 1) $ 中，$ n^3 $ 是增长最快的项，而 $ (n^2 + 1) $ 增长非常缓慢，基本可以忽略不计。

因此，整个表达式的主导项是 $ n! n^3 $，因为 $ n! $ 的增长速度远超过 $ 2^n $。

最好的大 $ O $ 估计：
$ O(n! n^3) $

总结：

• 1. $ O(n^3) $
• 2. $ O(n^5) $
• 3. $ O(n! n^3) $