１．講義概要
アルゴリズム：問題解決の手順
本講義では、アルゴリズムに関する様々なアイディアを紹介することを通して、コンピュータによる問題解決の基本的な考え方を身に付けることを目的としている。今回は整列法を例に、アルゴリズムを比較・評価する際の尺度について見てゆく。
最古（？）のアルゴリズム：ユークリッドの互除法
正整数 $m,n$ の最大公約数 $\gcd (m,n)$ を、
$\gcd(m,n)=\begin{cases}
\gcd(n,m \bmod n) & \\
n & m \bmod n=0 のとき
\end{cases}$
を利用して求める。（$m \bmod n$ は$m$を$n$で割った余り）
パズル．ユークリッドの互除法で一番手間（$\bmod$の計算回数）がかかる数値の組み合わせは、どのような場合か
ヒント．計算過程で常に $m \bmod n = m-n$ になる場合
２．アルゴリズムの評価基準
アルゴリズムの評価基準- 計算時間：出力を得るまでの時間
- 記憶容量：計算に必要なメモリー量
- 分かり易さ
| 評価基準 | 時間 | 記憶容量 | 分かり易さ | 備考 |
| 選択ソート | × | 〇 | ◎ | |
| クィックソート | ◎ | ○ | × | 最速 |
| 挿入ソート | △ | ○ | ○ | ほぼ整列データには速い |
| マージソート | ○ | △ | ○ | 外部記憶中の大量データに適用可能 |
| 基数ソート | ○ | △ | △ | データに制限有り |
３．整列(ソート)法の色々
計算時間は比較回数(赤色のデータ数)に比例選択ソート
「未整列部(赤)の最大値を右端と交換(青)」を繰り返す。
比較回数：$n(n+1)/2$
クイックソート
「未整列部[赤]を右端の値を基準に、以下[赤]と以上[赤]に分割」を繰り返す
比較回数：平均$n\log_2n$に比例、最悪$n(n+1)/2$
パズル：計算時間(単位ミリ秒)を計測・予測せよ。
| データ数 | 10000 | 20000 | 30000 | 1000000(予測) |
| 選択ソート | ||||
| データ数 | 1000000 | 2000000 | 3000000 | 100000000(予測) |
| クイックソート |
挿入ソート
「仮整列部(赤と緑)の直前データを適切な位置に挿入する」を繰り返す。（緑は挿入で不動だった部分、右端の赤は番兵）
比較回数：平均$n^2/4$
マージソート
「隣接する仮整列部([赤])を併合する」を繰り返す
比較回数：$n\log_2n$
パズル：計算時間(単位ミリ秒)を計測・予測せよ。
「仮整列部(赤と緑)の直前データを適切な位置に挿入する」を繰り返す。（緑は挿入で不動だった部分、右端の赤は番兵）
比較回数：平均$n^2/4$
マージソート
「隣接する仮整列部([赤])を併合する」を繰り返す
比較回数：$n\log_2n$
パズル：計算時間(単位ミリ秒)を計測・予測せよ。
| データ数 | 10000 | 20000 | 30000 | 1000000(予測) |
| 挿入ソート | ||||
| データ数 | 1000000 | 2000000 | 3000000 | 100000000(予測) |
| マージソート |
パズル：次の方法で整列できる。確かめよ
バケツソート
各値の累積頻度を求め、整列後の位置を計算
値の範囲が小さいときに有効
計算時間：(データ数＋値の個数)に比例
基数ソート
桁数・文字列長が一定のデータに有効
下の桁から順にバケツソートを繰り返す
計算時間：(データ数＋値の個数)×桁数⇒桁数一定ならデータ数$n$に比例
パズル：計算時間(単位ミリ秒)を計測・予測せよ。
- １桁目の値で分類し、順に並べる
- 1.の順に、2桁目で分類し順に並べる
- その繰り返し
バケツソート
各値の累積頻度を求め、整列後の位置を計算
値の範囲が小さいときに有効
計算時間：(データ数＋値の個数)に比例
基数ソート
桁数・文字列長が一定のデータに有効
下の桁から順にバケツソートを繰り返す
計算時間：(データ数＋値の個数)×桁数⇒桁数一定ならデータ数$n$に比例
パズル：計算時間(単位ミリ秒)を計測・予測せよ。
| データ数 | 1000000 | 2000000 | 3000000 | 100000000(予測) |
| 基数ソート |
４．オーダーの概念
アルゴリズムを実装したプログラムの実際の計算時間は- 使用するプログラミング言語によって異なる
- 実行するコンピュータ(さらに実行時の環境)によっても異なる
- 入力データのサイズによって異なる
- 指標となる適切な演算の実行回数に比例する
計算時間の見積もり手順
適切な演算を選ぶ
⇒ その実行回数を入力サイズの関数として表す
⇒ 小サイズのサンプル入力に対する計算時間を測る
⇒ 実際の入力(サイズ)での計算時間を見積もる
計算時間の増え方や基準サイズの計算時間の何倍になるかを問題にする立場
例えばサイズ$n$の入力に対する演算回数が$2n^2+5n$であるとき
$n$がある程度大きくなると、$5n$の項は$n^2$に比べて無視できるし
$n^2$の係数$2$も無関係
このとき、 $2n^2+5n$のオーダーは$n^2$であるという。
このように、(1変数)関数がいくつかの項の和で表されているときに、(変数の増加に伴う)増え方のもっとも大きな項を取り出し、その定数係数を無視したものを、その関数のオーダーという。
パズル．次の関数のオーダーを答よ。
（１）$3n^2+5$ （２）$n\log_2n+3n$ （３）$2^n+20n^3$
例えばサイズ$n$の入力に対する演算回数が$2n^2+5n$であるとき
$n$がある程度大きくなると、$5n$の項は$n^2$に比べて無視できるし
$n^2$の係数$2$も無関係
このとき、 $2n^2+5n$のオーダーは$n^2$であるという。
このように、(1変数)関数がいくつかの項の和で表されているときに、(変数の増加に伴う)増え方のもっとも大きな項を取り出し、その定数係数を無視したものを、その関数のオーダーという。
パズル．次の関数のオーダーを答よ。
（１）$3n^2+5$ （２）$n\log_2n+3n$ （３）$2^n+20n^3$
| パズル．表の空欄を埋めよ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
５．整列アルゴリズムの計算量
$n$はデータ数| 時間 | 記憶容量 | 備考 | |
| 選択ソート | $n^2$ | $n$ | |
| クィックソート | $n\log n$ | $n$ | 最速 |
| 挿入ソート | $n^2$ | $n$ | ほぼ整列データには速い |
| マージソート | $n\log n$ | $2n$または$1$ | 外部記憶中のデータに適用する場合の記憶容量は定数($1$) |
| 基数ソート | $nk$ | $n+m$ | $k$はデータの桁数。$m$はバケツの個数 |
６．ベキ乗計算アルゴリズム
$y^x$の素朴な計算法 $y^2,y^3,\dots,y^x$と$y$を順に掛ける$x-1$回の掛算⇒オーダー$x$の計算時間⇒$10^{xの桁数}$ の計算時間
桁数が1増えると10倍の時間（入力$x$のサイズは$x$の桁数）
Binary法 $x$の$2$進表示と、$y^1,y^2,y^4,y^8,\dots$の値を利用する
例．$22$は$2$進$5$桁の$10110$なので$y^{22}=y^{16+4+2}=y^{16}y^4y^2$。
$y^2,y^4,y^8,y^{16}$の計算($2$乗の掛算$4$回)と$y^{16}y^4y^2$の計算(掛算$2$回)で掛算$6$回
$x$が$2$進$k$桁の時 $\begin{cases}y^2, y^4,\dots,y^{2^{k-1}}の系列の計算にk-1回\\
組み合わせてy^xを計算するのに(最大)k-1回 \end{cases}$ 計$2k-2$回
オーダーは$x$の$2$進桁数($\log_2x$)：素朴法に比べ圧倒的に速い（オーダーの表）
パズル．MOD電卓(右上)で$y^x$の計算時間に関する次の問に答えよ($y$の値は任意)
- $x=10^6,10^7,10^8$に対し素朴法【yx】とBinary法【速yx】の計算時間を調べよ。
- $x=10^{15}$に対する【yx】の計算にはおおよそ何日かかるか。
ヒント：$x=10^8$乗に1秒かかれば$x=10^{15}$乗には$10^7秒/60/60/24\simeq116日$。