目次

1. オーダー記法
2. ソートアルゴリズム
3. グラフ
   1. グラフの基本用語
   2. 最小木
   3. 最短路
4. 動的計画法

1. オーダー記法

2. ソートアルゴリズム (1/)

1. バブルソート

アルゴリズム
$i = 1,2,\ldots,n-2;~ j=i,i+1,\ldots,n-1$ の順に以下の操作を行う．
> $A[j],A[j+1]$ を比較し，$A[j]>A[j+1]$ ならば要素を入れ替える．

正当性
$i=1$ のとき，最大要素が $A[n]$ に移動する．$i=2$ のとき，次に大きい要素が $A[n-1]$ に移動する．以下，帰納的に成り立つ．

計算量

より $O(n^2)$．

2. ソートアルゴリズム (2/)

2. マージソート

アルゴリズム

1. 長さ $n$ の配列 $A$ を長さ $n/2$ の左半分 $A_l$ と右半分 $A_r$ に分割する
2. $A_l,A_r$ を再帰的にそれぞれソートする
3. $A_l,A_r$ について，小さい方の要素から順にとっていくことで $A$ の整列集合を得る

正当性
帰納的に示す．$A_l,A_r$ が正しくソートされていると仮定する．このときステップ 3 で $A_l,A_r$ の要素を昇順に並べた配列，すなわち $A$ のソート済み配列が得られる．

計算量
漸化式 $T(n) = 2T(n/2) + cn$ より，$T(n) = O(n\log n)$ となる．

3. グラフ (3.1 グラフの基本用語)

3.2 最小木 (1/)

必要性（$\Rightarrow$）の証明
ある辺 $f\in C_e$ について $w(f) > w(e)$ と仮定する．このとき $T'=T\setminus\{f\}\cup\{e\}$ を考えると $w(T)>w(T')$ である．また $T$ は全域木である．（$\because$ 路が $f$ を使っていた場合，代わりに $C_e - f$ を使えばよい．）よって，$T$ の最小性に矛盾．

十分性（$\Leftarrow$）の証明
$T$ を右辺の条件を満たし最小木でない全域木とする．また，$T^\ast$ を $|T\setminus T^\ast|$ が最小になるような最小木とする．ある辺 $e\in T^\ast\setminus T$ を取りその端点を $u,v$ とすると，$e$ は $T^\ast$ を $2$ つの連結成分 $T^\ast_u,T^\ast_v$ に分割する．また，$T$ の基本閉路 $C_e$ を考えると，$C_e$ 上には端点がそれぞれ $T^\ast_u,T^\ast_v$ に含まれるような辺 $f$ が存在する．仮定より，$w(f)\le w(e)$ である．ここで，${T^\ast}' := T^\ast\setminus\{e\}\cup\{f\}$ とすると，$w({T^\ast}')\le w(T^\ast)$ かつ ${T^\ast}'$ が全域木であることから ${T^\ast}'$ は最小木．したがって $|T\setminus T^\ast|$ の最小性に矛盾.

4. 動的計画法