Yuchen You

有限集 我们称一个集合是有限的如果其等势于某个集合 [n][n][n] , 其中 [n]:={1,⋯ ,n}[n]:=\{1,\cdots, n\}[n]:={1,⋯,n} 鸽笼原理 pigeonhole principle 自然数集合 [n] 不等势与任何一个真子集 caveat 对于函数 f:A→Bf: A \to Bf:A→B 我们有 如果 A=∅A = \emptysetA=∅ 那么对于任意函数 f:∅→Bf :\emptyset \to Bf:∅→B 是单射的 如果 B=∅B = \emptysetB=∅ 则 fff 是一个空映射，从 ∅→∅\emptyset \to \emptyset∅→∅ 这也是满射的，因此这也是一个双射 推论 没有有限集能等势于其真子集 N\mathbb NN 是无限集 任意有限集合等势于一个唯一的自然数 任意有限集的子集是有限集 对于非空有限集合 A,BA,BA,B, 如果存在单射 f:A→Bf: A\to Bf:A→B, 那么 ∣A∣≤∣B∣|A| \le |B|∣A∣≤∣B∣ 如果 f:A→[n]f : A\to [n]f:A→[n] 是 ...

有向图和无向图

这篇文章参考了 知乎文章, 作者清华爷 @cronus-裁 傅里叶级数回忆 Bf={12π,1πcos⁡(nx),1πsin⁡(nx)}n=1∞B_f = \{\frac 1 {\sqrt{2\pi}},\frac 1{\sqrt{\pi}}\cos(nx),\frac 1{\sqrt\pi}\sin(nx)\}_{n=1}^\inftyBf​={2π​1​,π​1​cos(nx),π​1​sin(nx)}n=1∞​ 是平方可积空间 L2([−π,π])L^2([-\pi,\pi])L2([−π,π]) 的一组函数的基，对于空间中的任意函数，我们都有 f=lim⁡SNf = \lim S_Nf=limSN​ 拟合公式 SN(x)=⟨f,1⟩2π+Σn=1N⟨cos⁡(nx),f⟩πcos⁡(nx)+Σn=1N⟨sin⁡(nx),f⟩πsin⁡(nx)S_N (x) = \frac{\langle f,1\rangle}{2\pi}+\Sigma_{n=1}^N \frac{\langle \cos(nx),f\rangle}{\pi}\cos(nx)+\Sigma_{n=1}^N\fr ...

自然数的定义 大于：如果存在 k∈Nk\in \mathbb Nk∈N 使得 m+k=nm + k = nm+k=n 则有 n≥mn \ge mn≥m 整除：如果存在 k∈Nk\in \mathbb Nk∈N 使得 n=m⋅kn = m \cdot kn=m⋅k 则有 m∣nm | nm∣n 我们称为 m divides n 偶数：如果 2∣n2 | n2∣n 则 nnn 为偶数 奇数： ∃k∈N\exists k \in \mathbb N∃k∈N s.t. n=2k+1n = 2k + 1n=2k+1 质数 (prime): 不存在 k∈Nk\in \mathbb Nk∈N，1<k<n1 < k < n1<k<n 使得 k∣nk | nk∣n 那么我们称 n 是 prime 质数有无数个 两类证明方法： 我们假设质数是有限个，那么我们有有限集 P={p1⋯ ,pn}\mathbb P = \{p_1 \cdots ,p_n\}P={p1​⋯,pn​} 那么我们找到自然数 N=p1⋅p2⋯pn+1N = p_1 \cdot p_2 \cdot ...

O(1) — 常量空间复杂度 不管输入数据的规模如何，算法所需的内存空间大小是固定的。 数组中查找最大元素。这个操作只需要一个变量来保存当前找到的最大值，因此空间复杂度是O(1)。 O(log n) — 对数空间复杂度 需要的空间随输入数据的规模的对数增长。 递归实现的二分查找。在每次递归调用中，问题的规模都减半，因此最大的调用深度是log n，相应地，栈的空间也是O(log n)。 O(n) — 线性空间复杂度 需要的空间与输入数据的规模成正比。 动态数组（如C++中的 std::vector）。动态数组可能需要根据输入数据的数量动态调整大小，其空间复杂度通常是O(n)。 O(n log n) — 线性对数空间复杂度 空间复杂度介于线性和平方之间，通常见于一些特殊的排序算法中。 归并排序。在归并排序中，虽然每次合并操作都需要O(n)的空间，但由于其递归的性质，通常需要O(log n)层递归调用，因此整体的空间复杂度可能表现为O(n log n)。 O(n^2) — 平方空间复杂度 需要的空间与输入数据的规模的平方成正比。 一些特定的算法问题，如存储一个n x n的二维数组。

关系 Relation 定义 对于子集 R⊂A×BR\subset A\times BR⊂A×B 称为 a relation from A to B domain: domain(R):={x∣∃y（xRy)}\text{domain}(R) := \{x|\exists y（xRy)\}domain(R):={x∣∃y（xRy)} 定义域是使得 R 成立的第一个元素的集合 range: image(R):={y∣∃x(xRy)}\text{image}(R):=\{y|\exists x(xRy)\}image(R):={y∣∃x(xRy)} 值域表示 R 成立的第二个元素的集合 符号表述法 notation (x,y)∈R⇔xRy(x,y)\in R \Leftrightarrow xRy(x,y)∈R⇔xRy (x,y)∉R⇔xR̸y(x,y)\not\in R\Leftrightarrow x\not R y(x,y)​∈R⇔x​Ry 如果 A=BA = BA=B 我们称 RRR 是一个 relation on A 还原关系 identity relation idA={ ...

O(1) 常见的就是直接访问一个数组中某个元素的内容 这种算法一般不会受到输入数据大小的影响 1return array[i]; O(n) 线性时间复杂度，一般是遍历一阶数组中的所有元素 这会随着输入数据量的大小线性增大 O(log n) 对数时间复杂度，一般自常见的是用在对分查找。 或者常见的 m 叉树结构我们有 O(logmn)O(log_m n)O(logm​n) 的时间复杂度 O(n log n) - 线性对数时间复杂度 归并排序或快速排序。 说明：这些排序算法在最好或平均情况下的时间复杂度为n log n。 具体的算法的时间复杂度我们会在后面的细节讲解中提及. O(n^2) - 平方时间复杂度 冒泡排序或选择排序。 说明：这类算法通常涉及双重循环，对每对输入元素都进行操作。 容易搞混的地方在于，我们看每一层循环都容易看出是 一阶复杂度，然后我们会认为直接加起来就是一阶求和还是一阶复杂度，这就不对了 冒泡排序的时间复杂度推导 从最差角度考虑，冒泡排序需要比较 + 替换相邻元素的次数是 (n−1)+⋯+1=n(n−1)2(n - 1) + \cdots + 1 = \frac{n ...

复频域的意义 在复频域中，函数 F(s) 的变量 s 表示的是复平面上的一个点，这个平面被称为 s 平面（s-plane）。这个平面的实部 σ 和虚部 ω 分别对应着衰减和振荡的特性： 实部 σ：表示信号的衰减或增长速度。 虚部 ω：表示信号的振荡频率。 通过拉普拉斯变换，我们可以从 F(s) 中分析系统的稳定性、响应特性等。 应用示例 例如，对于一个线性时不变系统（LTI system），其输入输出关系可以用微分方程表示。通过对这个微分方程应用拉普拉斯变换，可以将其转换为一个代数方程，这样就可以更方便地求解系统的传递函数（transfer function）和频率响应（frequency response）。 拉普拉斯和傅里叶 这是拉普拉斯变换公式 L{f(t)}=F(s)=∫0∞e−stf(t) dt\mathcal{L}\{f(t)\} = F(s) = \int_{0}^{\infty} e^{-st} f(t) \, dt L{f(t)}=F(s)=∫0∞​e−stf(t)dt 这是傅里叶变换公式 F{f(t)}=F(ω)=∫−∞∞f(t)e−jωt dt\mathcal{ ...

有效性 对于一个正整数集合任何非空子集，必然有最小的元素存在，假定知道 P(1)P(1)P(1) 为真，我们可以从 P(k)→P(k+1)P(k)\to P(k+1)P(k)→P(k+1) 这个依赖于正整数的良序性 良序性公理 Well-Order-Principle 任意一个非空的非负整数集合都有最小元素 数学归纳原理 首先给一个谓词 P:N→BP : \mathbb N \to \mathbb BP:N→B 且表示 P(n)P(n)P(n) 为真对于所有 n∈Nn\in \mathbb Nn∈N 成立 基础条件 / 边界条件 base case 证明 P(0)P(0)P(0) 为真 递推条件 inductive case 这个需要有一个递推的假设，我们写作 inductive hypothesis 或者缩写为 IH 然后证明 (∀n∈N)(P(n)→P(n+1))(\forall n \in \mathbb N)(P(n)\to P(n+1))(∀n∈N)(P(n)→P(n+1)) 除法定理 Division Algorithm 对于 m,n∈Nm, n \in \mathbb N ...

语义等价、满足性和有效性 真值表一致并不能表明我们的逻辑语义就是等价的，比如我们有 蕴含关系， 这和 ¬p∨q\neg p \lor q¬p∨q 是不等价的 定义 对于命题逻辑公式 ϕ\phiϕ 和 ψ\psiψ, 我们称二者语义等价，当且仅当 ϕ⊨ψ∧ψ⊨ϕ\phi\models \psi \land \psi \models \phiϕ⊨ψ∧ψ⊨ϕ 成立，记为 ϕ≡ψ\phi \equiv \psiϕ≡ψ. 进一步, 如果 ⊨ϕ\models \phi⊨ϕ 成立，我们称 ϕ\phiϕ 是有效的 引理 命题逻辑公式 ϕ1⋯ϕn⊨ψ\phi_1\cdots\phi_n\models \psiϕ1​⋯ϕn​⊨ψ成立，当且仅当 ⊨ϕ1→(ϕ2⋯→(ϕn→ψ))\models\phi_1\to(\phi_2\cdots\to(\phi_n \to \psi))⊨ϕ1​→(ϕ2​⋯→(ϕn​→ψ)) 这个引理用于将命题变成完全不包含 →\to→ 的形式 （使用 ¬p∨q≡p→q\neg p\lor q\equiv p\to q¬p∨q≡p→q tautology) 通过将 →\to→ 变成一般 ...