跳转至

离散数学

离散数学

chap1 and chap2 记到了平板上

Chap3 Algorithms

2.1

1 搜索算法

鉴于和 fds 重合度过高，这里不再赘述

2 greedy algorithms

Greedy Change-Making Algorithm（贪心找零算法）用于解决找零问题：给定不同面值的硬币，如何使用最少数量的硬币凑出目标金额。

1. 贪心策略

  • 每次选择当前面值最大且不超过剩余金额的硬币。
  • 重复这个过程，直到找零完成。

这种方法在 某些货币系统（如美金、人民币的常规硬币面值）下能保证最优解，但对 任意硬币系统 并不一定最优（可能需要动态规划）。

2. C 语言实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
c复制编辑#include <stdio.h>

// 计算找零所需的最少硬币数
void greedyChange(int coins[], int n, int amount) {
   int count[n];  // 记录每种硬币使用的数量
   for (int i = 0; i < n; i++)
       count[i] = 0;

   printf("Change for %d using Greedy Algorithm:\n", amount);

   for (int i = 0; i < n; i++) {
       while (amount >= coins[i]) {
           amount -= coins[i];
           count[i]++;
       }
   }

   for (int i = 0; i < n; i++) {
       if (count[i] > 0)
           printf("Coin %d: %d\n", coins[i], count[i]);
   }

   if (amount > 0)
       printf("Remaining amount: %d (cannot be changed exactly)\n", amount);
}

// 主函数
int main() {
   int coins[] = {25, 10, 5, 1};  // 硬币面值（以美分为例）
   int n = sizeof(coins) / sizeof(coins[0]);
   int amount;

   printf("Enter the amount in cents: ");
   scanf("%d", &amount);

   greedyChange(coins, n, amount);

   return 0;
}

3. 代码解析

  1. 贪心选择：优先使用面值最大的硬币。
  2. 循环检查：每次选择硬币后更新剩余金额。
  3. 存储硬币个数：count[] 数组记录每种硬币的使用数量。
  4. 特殊情况：如果找零不能刚好分配（如面值不兼容），则会输出“无法完全找零”。

2.2

时间复杂度和空间复杂度分析

时间复杂度 O(N)定义

这部分定义的是**大 O 记号（Big-O Notation），用于描述一个函数的**渐近上界，即当 \(x\) 足够大时，\(f(x)\) 的增长速率不会超过 \(g(x)\) 的某个常数倍。

逐步解析

  1. \(f(x)\) 和 \(g(x)\) 是从整数（\(\mathbb{Z}\)）或实数（\(\mathbb{R}\)）到实数（\(\mathbb{R}\)）的函数

    • 也就是说，\(f(x)\) 和 \(g(x)\) 是定义在整数或实数上的函数，值域都是实数。

  2. “\(f(x)\) 是 \(O(g(x))\)” 的定义：

    \[ |f(x)| \leq C |g(x)| \quad \text{whenever } x > k \]
    • 存在常数 \(C\) 和 \(k\)，使得当 \(x > k\) 时，\(|f(x)|\) 总是小于等于某个常数倍的 \(|g(x)|\)。
    • 解释： 这意味着，当 \(x\) 足够大时，\(f(x)\) 的增长不会超过 \(g(x)\) 的某个倍数。

举个例子

假设 \(f(x) = 3x^2 + 5x + 7\)，\(g(x) = x^2\)，我们想证明：

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

即 \(f(x)\) 的增长速度不会超过 \(x^2\) 的某个倍数。

步骤 1：寻找合适的 \(C\) 和 \(k\)

我们希望找到 \(C\) 和 \(k\) 使得：

\(|3x^2 + 5x + 7| \leq C |x^2| \quad \text{for } x > k\)

  • 当 \(x\) 足够大时，最高阶项 \(3x^2\) 是主要的影响因素，其他项 \(5x\) 和 \(7\) 可以忽略。

  • 取 \(k = 1\)，我们估算：

\(3x^2 + 5x + 7 \leq 3x^2 + 5x^2 + 7x^2 = 15x^2\)

  • 这里使用了 \(5x \leq 5x^2\) 和 \(7 \leq 7x^2\)，当 \(x > 1\) 时成立。

  • 取 \(C = 15\)，那么对于 \(x > 1\)，有：

\(3x^2 + 5x + 7 \leq 15x^2\)

说明 \(f(x)\) 是 \(O(x^2)\)。

✅ 结论：\(f(x) = O(x^2)\)，即 \(f(x)\) 的增长不会超过 \(x^2\) 的 15 倍。

直观理解

  • \(O(g(x))\) 表示 \(f(x)\) 在大范围内的增长速率不会超过 \(g(x)\) 的某个倍数。
  • 不关心具体的常数系数和小 \(x\) 的情况，只关心极限情况下的增长趋势。
  • 在算法分析中，通常选择最小的 \(g(x)\) 来表示增长速率，例如 \(O(n^2)\) 比 \(O(n^3)\) 更精确地描述一个算法的复杂度。

常见的渐近增长阶

记号 常见示例 说明
\(O(1)\) 常数时间操作，如 return 1 计算量不随输入增长
\(O(\log n)\) 二分查找 对数增长
\(O(n)\) 线性搜索 线性增长
\(O(n \log n)\) 归并排序、快速排序 介于线性和平方之间
\(O(n^2)\) 冒泡排序 平方增长
\(O(2^n)\) 斐波那契递归 指数增长，最慢

以上内容来自 gpt

复杂度排序

以下是常见算法的时间复杂度排序，从最好（最优）到最差（最劣）：

复杂度 名称 描述
O(1) 常数时间（Constant） 计算次数不随输入大小变化，如哈希查找
O(log n) 对数时间（Logarithmic） 每次操作都减少问题规模，如二分查找
O(n) 线性时间（Linear） 处理每个元素一次，如顺序查找
O(n log n) 线性对数时间（Linearithmic） 高效排序算法，如归并排序、快速排序（平均情况）
O(n²) 平方时间（Quadratic） 双重嵌套循环，如冒泡排序、插入排序
O(n³) 立方时间（Cubic） 三重嵌套循环，如 Floyd-Warshall 算法
O(2ⁿ) 指数时间（Exponential） 递归解决子问题，如斐波那契递归
O(n!) 阶乘时间（Factorial） 全排列问题，如旅行商问题暴力解法

2.3 Complexity of algorithms

2.3.1 time comlexity

3892882380e51a0b57568538555ab72

注：计算复杂度一般不包含赋值语句，然后 if-else 一般要算两次

2.3.2

算法复杂性的理解

1. 可解问题分类

  • 可处理问题 (Tractable): 存在一个算法可以在多项式时间内解决该问题。
  • 不可处理问题 (Intractable): 不存在多项式时间算法可以在最坏情况下解决该问题。

2. 可解性

  • 可解问题 (Solvable): 存在算法可以解决该问题。
  • 不可解问题 (Unsolvable): 存在某些问题，理论上可以证明没有任何算法能够解决它们。

3. 停机问题 (Halting Problem)

  • 问题描述：给定一个程序和一个输入，判断程序在该输入下是否会最终停止。
  • 数学定义: \(K = \{(i, x) | \text{程序 } i \text{ 在输入 } x \text{ 下最终会停止} \}\)
  • 该问题是**不可解的**，即不存在一个通用算法可以正确判断任意程序是否会停机。
2.3.3 算法复杂性分析

1. P 类问题 (Class P)

  • 定义: 可处理问题，即可以在多项式时间内求解的问题。

2. NP 类问题 (Class NP, Nondeterministic Polynomial Time)

  • 定义: 不能保证多项式时间内求解，但如果给出一个候选解，可以在多项式时间内验证其正确性的问题。

3. NP 完全问题 (NP-complete)

  • 定义
这是一类特殊的 NP 问题，具有如下性质：
  1. 属于 NP 类问题（即解可以在多项式时间内验证）。
  2. NP-完全性: 如果找到一个可以在多项式时间内求解的 NP 完全问题（即 P=NP），那么所有 NP 问题都可以在多项式时间内求解。

4. 可满足性问题 (SAT, Satisfiability Problem)

  • 问题描述: 给定一个布尔公式，判断是否存在一种变量赋值，使得公式计算结果为 TRUE。
  • 意义: 这是第一个被证明为 NP 完全的问题（库克定理，Cook's Theorem），在计算复杂性理论中极为重要。

Chap 5 mathermatical induction

数学归纳法

  • basis step : establish p(1)
  • p(k)->p(k+1)

so we can make the conclusion

第一数学归纳法和第二数学归纳法

5.2 strong induction and well-ordering

强归纳法与良序性

Chap 6

你这个题目其实是著名的 Ramsey 定理 的特例，常见的叫法是 “六人定理”，也可以看作是 一般化鸽巢原理 的一个应用。

我来帮你把完整的证明思路补全一下，让你一看就懂：

已知条件

  • 总共 6 个人，记作 \(a_1, a_2, a_3, a_4, a_5, a_6\)。
  • 每两个人要么是朋友，要么是敌人。
  • 要证明：一定存在 3 个人互为朋友，或者 3 个人互为敌人。

证明：

Step 1: 固定其中一个人，假设是 \(a_1\)。

那么 \(a_1\) 和其它 5 个人之间，每个人要么是朋友，要么是敌人。

Step 2: 根据**鸽巢原理**：

  • 5 个人分成两类：朋友 or 敌人。
  • 5 个人分到两个“巢”里，至少有 \(\lceil 5/2 \rceil = 3\) 个人落在同一个巢里。

所以必有：

  • \(a_1\) 至少有 3 个朋友，或者
  • \(a_1\) 至少有 3 个敌人。

Step 3: 分两种情况：

Case 1：假设 \(a_1\) 有三个朋友 \(a_i, a_j, a_k\)

现在看 \(a_i, a_j, a_k\) 三人之间的关系。

  • 如果他们之中有任意两个是朋友，比如 \(a_i\) 和 \(a_j\) 是朋友，则 \(\{ a_1, a_i, a_j \}\) 就是**三个互为朋友**的团体。
  • 如果 \(a_i, a_j, a_k\) 之间都互相是敌人，那么 \(\{ a_i, a_j, a_k \}\) 就构成了**三个互为敌人**的团体。

Case 2：假设 \(a_1\) 有三个敌人 \(a_i, a_j, a_k\)

同理：

  • 如果 \(a_i, a_j, a_k\) 中任意两个互为敌人，比如 \(a_i\) 和 \(a_j\) 是敌人，则 \(\{ a_1, a_i, a_j \}\) 就是**三个互为敌人**的团体。
  • 如果 \(a_i, a_j, a_k\) 中都互为朋友，则 \(\{ a_i, a_j, a_k \}\) 就是**三个互为朋友**的团体。

结论

不管是 Case 1 还是 Case 2，总可以找到：

  • 三个人互为朋友，或者
  • 三个人互为敌人。

证毕！

这个其实就是 \(R(3,3) = 6\) 的经典证明。

很好！你现在展示的是 Ramsey 数 \(R(m, n)\) 的定义。

通俗解释就是：

\(R(m, n)\) 是最小的 \(N\)，使得不管你怎么安排 \(N\) 个人的关系（朋友 or 敌人），总能在里面找到：

  • \(m\) 个两两互为朋友，或者
  • \(n\) 个两两互为敌人。

刚才我们做的那个题目其实就是在求 \(R(3,3)\)，它的值恰好是 6。

也就是说：

\(R(3,3) = 6\)

意思是：

  • 只要有 6 个人，不管你怎么安排他们的朋友关系和敌人关系，一定存在 三个互为朋友 或 三个互为敌人。

如果你以后学更深的组合数学、图论，Ramsey 数是很重要的概念！

顺便告诉你几个常见的 Ramsey 数值：

\(R(m, n)\) 数值
\(R(3,3)\) 6
\(R(4,3)\) 9
\(R(4,4)\) 18
\(R(5,5)\) ?（至今没确定，只知道在 [43,49] 之间）

所以，这个定理还有一个很有名的外号叫：

在任何 6 人的聚会中，总有 3 个互为朋友或者 3 个互为敌人。

如果你愿意，我可以顺手帮你整理：

  1. 更完整的笔记
  2. 配一张小图示
  3. 帮你列出常见的 Ramsey 数表

会对你理解和记忆很有帮助，要不要？你只需要回我【要】就行~