Problem Solving

正确性证明 Loop invariants Initialization Maintenance Termination 时间复杂度 cost: 硬件执行一条指令的代价 times: 指令被执行的次数 running time 计算方法 : $T(n)=\sum c i n i$ worst case running time average case ru...

排序 插入排序 循环不变量：每次循环开始前，子数组 A[1..j 1] 有序 worst: $\Theta(n^2)$ average: $\Theta(n^2)$ 归并排序 worst case: $\Theta(n\lg n)$ average case: $\Theta(n\lg n)$ 堆排序 worst case: $O(n\lg n)$ not...

Dynamic sets operations Search(S, k) Insert(S, x) Delete(S, x) Min/Max(S) Successor(S, x) Precessor(S, x) data structure augmentation choose an underlying data structure determine...

brute force 枚举：遍历解空间 倍增：保存 $2^i$ 处的解用于构造所有情况 递归：原问题划归到一个子问题 搜索：建立树/图模型，以一定次序穷举 模拟 剪枝：利用数学性质缩小解空间 前缀和、差分 打表：将不同问题的解储存 Divide and Conquer 分治法 Examples: 归并排序： $T(n)=2T(n/2)+\Theta(n)$...

Introduction Graph $G=(V,E)$ order $|V|$ incident $u\sim v$: u and v are neighbors walk $W = (u=v 0, v 1, \dots, v k = v)$ open walk: $u\neq v$ closed walk: $u=v$ trail: $u$ $v$ wa...

Definition Alphabet $\Sigma$: alphabet $\Sigma^ =\mathcal{P}(\Sigma)$ $\Sigma^+=\Sigma^ \{\lambda\}$ $s\in\Sigma$: symbol $s\in w$ $w\subseteq\Sigma, \omega\in\Sigma^ $: word over...

背景知识 自然数的集合论定义： $a^+:=a\cup\{a\}$ 归纳集 $\emptyset\in A$ $\forall a(a\in A\rightarrow a^+\in A)$ $\mathbb{N}$ 为所有归纳集之交 Peano 结构 $e\in S$ $\forall a\in S,f(a)\in S$ $\forall b\in S,\f...

概论 密码系统：$(\mathcal{K}, \mathcal{M}, \mathcal{C})$ $\mathcal{K}$ 所有可能秘钥组成的集合 $\mathcal{M}$ 所有可能明文组成的集合 $\mathcal{C}$ 所有可能密文组成的集合 密码：$(E,D)$ $E$: 加密算法 $\mathcal{M}\times\mathcal{K}\r...