算法和数据结构

Week1 : 树

概念

vollständige Baum 完全树(所有节点有相同孩子个数)
$k$-verzweigte Baum k叉树

数学归纳法

证明完全二叉树的深度为 $log_{2}(n+1)$

Induktionsanfang:

==n = 1==: Laut induktiver Definition enthält jeder Unterbuam mindestens einen Knoten. n=1 bedeutet also, dass der Baum ein Blatt ist. Die Tiefe ist 1. Zu zeigen ist also: $1 \leq \log _{2}(n+1)$ . Es gilt $\log _{2} 2=1 \geq 1$

Induktionsvoraussetzung:

==Für alle $k \leq n$ gilt, dass== die Tiefe eines s vollständigen 2-verzweigten Baumes mit $k$ Knoten höchstens $log_{2}(k + 1) $ist.

Induktionsschritt:

==Betrachte Bäume mit $n+1$ Knoten.== Fallunterscheidung:

Es existiert ein $k \in\{1,2,3, \ldots\}$ mit $n + 1 = 2^{k} − 1$. (n+1是2的次幂-1) Weil der Baum $n + 1$, also mindestens zwei Knoten besitzt, kann er kein Blatt sein. Es gibt also $2$ Unterbäume, die jeweils höchstens n Knoten besitzen, da ein innerer Knoten schon vergeben ist. Laut IV ist die Tiefe der Unterbäume jeweils höchstens $\log _{2}(n+1)=\log _{2}\left(2^{k}-1\right)<k$. Da die Tiefe kleiner als $k$ und eine ganze Zahl ist, kann sie höchstens $k −1$ sein. Damit ist die Tiefe des gesamten Baumes höchstens $k=\log _{2}(n+1+1)$, was zu zeigen war.
Es existiert kein $k \in\{1,2,3, \ldots\}$ mitt $n + 1 = 2^{k} − 1$. Dann gibt es auch keinen vollständigen 2-verzweigten Baum mit $n + 1$ Knoten, und es ist nichts zu zeigen. Dass es zu allen vollst¨andigen 2-verzweigten Bäumen ein k gibt, so dass die Zahl der Knoten$2^{k}-1$ ist, kann man mittels Induktion nach der Tiefe t des Baumes zeigen. Für $t = 1 $ gilt $k = 1$, fur einen vollständigen 2-verzweigten Baum der Tiefe t+1 gibt es dann nach IV ein entsprechendes k fur die Unterbäume der Tiefe t, und weil die Unterbäume gemäß Definition gleich sind, ist das k ebenfalls gleich, d.h. die Gesamtzahl der Knoten ist

$1+2\left(2^{k}-1\right)=1+2^{k+1}-2=2^{k+1}-1$

Week 2 复杂度

公式

组合数放缩: \[ \left(\begin{array}{c}n-1 \\ i\end{array}\right)=\left(\begin{array}{c}n-1 \\ n-1-i\end{array}\right) \leq n^{n-1-i} \] 二项式定理: \[ (x+y)^{k}=\sum_{i=0}^{k}\left(\begin{array}{l} k \\ i \end{array}\right) x^{k-i} y^{i}=\sum_{i=0}^{k}\left(\begin{array}{l} k \\ i \end{array}\right) x^{k} y^{k-i} \] 倒着加和不编: \[ \sum_{i=0}^{n-1} i=\sum_{i=0}^{n-1} n-i-1 \]

重要结论

阶乘放缩 \[ n ! \geq n^{n / 2}=\sqrt{n}^{n} \]

Asymptotische Notation

增长不比 $f$ 快

\[ O(f(n))=\left\{g(n) \mid \exists c>0 \exists n_{0}>0 \forall n \geq n_{0}: g(n) \leq c \cdot f(n)\right\} \]

增长不必 $f$ 慢

\[ \Omega(f(n))=\left\{g(n) \mid \exists c>0 \exists n_{0}>0 \forall n \geq n_{0}: g(n) \geq c \cdot f(n)\right\} \]

与 $f$ 增长相同

\[ \Theta(f(n))=O(f(n)) \cap \Omega(f(n)) \]

比 $f$ 增长慢

\[ o(f(n))=\left\{g(n) \mid \forall C>0 \exists n_{0}>0 \forall n \geq n_{0}: g(n) \leq C \cdot f(n)\right\} \]

比 $f$ 增长快

\[ \omega(f(n))=\left\{g(n) \mid \forall C>0 \exists n_{0}>0 \forall n \geq n_{0}: g(n) \geq C \cdot f(n)\right\} \]

运算性质

\[ \begin{array}{l} \Theta(f(n)) \subseteq O(f(n)) \\ \Theta(f(n)) \subseteq \Omega(f(n)) \\ \Theta(f(n))=O(f(n)) \cap \Omega(f(n)) \\ o(f(n)) \subseteq O(f(n)) \\ \omega(f(n)) \subseteq \Omega(f(n)) \\ \omega(f(n)) \cap o(f(n))=\varnothing \end{array} \]

交换性质

\[ f(n) \in \mathcal{O}(g(n))\Rightarrow g(n) \in \Omega(f(n)) \\ f(n) \in o(g(n))\Rightarrow g(n) \in \omega(f(n)) \]

传递性

\[ f(n) \in o(g(n)) \quad \quad g(n) \in \mathcal{O}(h(n)) \quad \Rightarrow \quad f(n) \in o(h(n)) \\ f(n) \in \omega(g(n)) \quad \quad g(n) \in \mathcal{\Omega}(h(n)) \quad \Rightarrow \quad f(n) \in \omega(h(n)) \]

Week 3

求期望运行时间

把每一种情况出现的概率用期望加起来 \[ \begin{aligned} \mathbb{E}[X] &=\mathbb{E}\left[\sum_{i=1}^{k} X_{i}\right]=\sum_{i=1}^{k} \mathbb{E}\left[X_{i}\right]=\sum_{i=1}^{k} \mathbb{P}\left[X_{i}=1\right]=\sum_{i=1}^{k} \frac{1}{2^{i-1}} \\ &=\sum_{i=0}^{k-1}\left(\frac{1}{2}\right)^{i}=\frac{\left(1 / 2^{k}\right)-1}{1 / 2-1}=\frac{1-\left(1 / 2^{k}\right)}{1 / 2}=2-(1 / 2)^{k-1} \end{aligned} \]

求平均复杂度

把所有情况的复杂度加起来取平均值

$T(I)$ 是每一种情况运行的时间， $p(I)$ 是每一种情况出现的概率. 加权加起来就是了

Week 4

均摊分析 - 账本方法

$T(\sigma)$ 是一个操作 $\sigma \in S$ 的实际运行时间. 所有有一个序列 $\left(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{m}\right)$ 的操作运行时间 $T\left(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{m}\right):=\sum_{i=1}^{m} T\left(\sigma_{i}\right)$

定义函数 $\Delta: S \rightarrow \mathbb{R}$ 有如下的性质

对于所有操作序列 $\sum_{i=1}^{m} \Delta\left(\sigma_{i}\right) \geq 0$
$\Delta$ 尽可能好

这个函数是账户的数目变换，若 $\Delta(\sigma)>0$ 那么账户收入，如果 $\Delta(\sigma)<0$ 那么账户支出. \[ A(\sigma):=T(\sigma)+\Delta(\sigma) \] 是均摊运行时间.

于是一个序列的均摊时间是 \[ A\left(\sigma_{1}, \ldots, \sigma_{m}\right)=\sum_{i=1}^{m} A\left(\sigma_{i}\right)=\sum_{i=1}^{m}\left(T\left(\sigma_{i}\right)+\Delta\left(\sigma_{i}\right)\right) \\ =T\left(\sigma_{1}, \ldots, \sigma_{m}\right)+\underbrace{\sum_{i=1}^{m} \Delta\left(\sigma_{i}\right)}_{\geq 0} \geq T\left(\sigma_{1}, \ldots, \sigma_{m}\right) \]

Week 6

Universelles Hashing

主定理 Master Theorem

$a \geq 1, b \geq 1$ 且 $\epsilon>0$ . 考虑递归式 \[ T(n)=a T\left(\frac{n}{b}\right)+f(n) \]

Case 1: $f(n)=\mathcal{O}\left(n^{\log _{b}(a)-\epsilon}\right)$ , $T(n)=\Theta\left(n^{\log _{b} a}\right)$
Case 2: $f(n)=\Theta\left(n^{\log _{b}(a)} \log ^{k} n\right)$ , $T(n)=\Theta\left(n^{\log _{b} a} \log ^{k+1} n\right)$
Case 3: $f(n)=\Omega\left(n^{\log _{b}(a)+\epsilon}\right)$ , 且对于足够大的 $n$ 和 $c < 1$ 满足 $a f\left(\frac{n}{b}\right) \leq c f(n)$ , $T(n)=\Theta(f(n))$

Week 9 堆

二叉堆

操作

build构造

把数组依次按顺序填入二叉树(从上到下，从左到右). 然后自底向上shiftdown()调整
insert

把数字插入到二叉树最后一个位置，然后自底向上 shiftdown()
deleteMin

把最小值和最后一个位置交换，删除，然后对首元素 shiftdown()
decreaseKey

减小之后shiftUp
delete

和最后一个元素交换删除，然后shiftUp,然后shiftdown

二项堆

操作

insert

直接加在链表上
deleteMin

删掉最小的，然后merge
merge

先加到链表上，然后从小到大按rank合并

性质

Rang = Tiefe = $r$
第 $\ell \in\{0, \ldots, r\}$ 深度有 $\left(\begin{array}{l} r \\ \ell \end{array}\right)$ 个节点
总节点个数 $\sum_{\ell=0}^{r}\left(\begin{array}{l} r \\ \ell \end{array}\right)=2^{r}$