はじめに
インターン先でプログラミングを勉強中の文系学生。
「プログラマーとして働いていきたいなら、最低限のアルゴリズムは習得しておかないとね」
よし!! 今日はアルゴリズムを勉強していこう!!
アルゴリズムとは
最低限というか、基本的なアルゴリズムを学ぶ際にオススメのサイトとして、一週間で身につくアルゴリズムとデータ構造を紹介してもらった。
このサイトに沿って、勉強を進めていくことにしよう。
まずは、「アルゴリズム」が何なのかについて学んでいくか。
自分もある程度はプログラミングに触れてきたら、なんとなくの印象でしか言えないけれど、「アルゴリズム」＝「動作ごとに決められた型」。
簡単に言えば、「こういう処理をしたいなら、こういう風に書こう!!」みたいな?
実際はどうなんだろ?
教えてもらったサイトによると、料理における調理の方法や囲碁や将棋の定石に例えられている。
詳しい説明とかを見ていくと、「アルゴリズム」=「数学の公式」だね。
決められた型を使って、最適な方法で問題を解決する
それがアルゴリズム。
アルゴリズムの三大処理
アルゴリズムには基本となる3つの処理があるらしい。
なんでもすべてのアルゴリズムは、それらから構成されていて、そういう方法論を「構造化プログラミング」というんだって。
一体、どんな処理何だろう?
１つずつ見ていくか。
順次処理
順番通りに処理を実行するアルゴリズム。
PHPなら、
$n = 1;
$m = 1;
$sum = $n + $m;
echo $sum;
みたいな処理かな。
分岐処理
条件によって処理の流れを変えるアルゴリズム。
PHPなら、
$n = 5;
if($n < 10){
echo '10未満';
}else{
echo '10以上'};
みたいな処理かな。
繰り返し処理
定めた条件が成り立つ間処理を繰り返すアリゴリズム。
PHPなら、
for($i = 1;$i < 11;$i++){
echo $i;
}
みたいな処理かな。
ただ、これらの3つが組み合わさっていれば、アルゴリズムとして認められるわけではないらしい。
正式な(?)アルゴリズムとして認められるためには、正当性と停止性が必要とのこと。
これについても確認してみよう。
正当性
指定された条件を満たす入力がされた際に、正確に動作をする(正しい出力をする)ことが保証されていること
正当性が保証されているかどうかを知るためには、アサーションを用いられる。
アサーションとは、「任意の意思でアルゴリズムを停止しても、その時点で求められている条件が成立しているかどうか」を知ること。
成立していれば、その時点までの構文は正しいとされるため、部分正当性とも言われる。
停止性
どのようなアルゴリズムも最終的には停止する。
そのため、いかなる条件の入力値が与えられても、有限時間内に正しく停止されている事が保証されていなければならない。
ループ処理の判定に使われる変数などを確認し、無限ループに陥らないことが必要。
これで、アルゴリズムは3つの処理と2つの性質から成り立っていることがわかったっぞ。
時間に関するアルゴリズム
じゃあ、早速アルゴリズムについてみていこうっと。
最初は時間に関するアルゴリズムから。
時間→秒
時間を秒で示す場合、
h(時間)×3600+m(分)×60+s(秒)
となる。
それぞれを秒に換算にして、最後に合計するってことだよね。
秒→時間
与えられた秒数をtとすると、
t / 3600 = h(時間)
t % 3600 = i(時間では割り切れなかった秒数)
n / 60 = m(分)
n % 60 = s(秒)
見てみると簡単そうだけど、書くのはめんどくさそう…。
時間差を求めるアルゴリズム
上の2つを使って、時間の差を求めるアルゴリズムをPHPで作ると下のようになる。
例として、19時20分32秒と20時34分12秒の差を求めるとしよう。
$h1 = 19;
$m1 = 20;
$s1 = 32;
//19時20分32秒
$h2 = 20;
$m2 = 34;
$s2 = 12;
//20時34分12秒
$ha = $h1 * 3600;
$ma = $m1 * 60;
//$h1,$m1を秒に換算
$hb = $h2 * 3600;
$mb = $m2 * 60;
//$h2,$m2を秒に換算
$time1 = $ha + $ma + $s1;
$time2 = $hb + $mb + $s2;
//それぞれの時間を秒数に換算した結果
$d = 0;
//時間の差を入力するための変数
if($time1 > $time2){
$d = $time1 - $time2;
}else{
$d = $time2 - $time1;
};
$h = 0;
$n = 0;
$m = 0;
$s = 0;
//$dを〇時〇分〇秒で表示するために必要な変数
$h = $d / 3600;
//時間を求める
$n = $d % 3600;
$m = $n / 60;
//分を求める
$s = $m % 60;
//秒を求める
echo $h1.'時'.$m1.'分'.$s1.'秒と'.$h2.'時'.$m2.'分'.$s2.'秒'の差は、$h.'時間'.$m.'分'.$s.'秒';
これで良いのかな?
配列のアルゴリズム
続いて、配列のアルゴリズム。
その中でも基本的な、配列に格納されている数字の合計を求めるアルゴリズムと配列の中で最大値を求めるアルゴリズムについて学んでいこう。
配列に格納されている数字の合計を求めるアルゴリズム
言葉で説明するよりも、コードの方がわかりやすいよね。
$n = array(1,2,3,4);
$sum = 0;
for($i = 0;$i < 4;$i++){
$sum += $n[$i]
}
echo $sum;
配列の中で最大値を求めるアルゴリズム
これもコードのほうがわかりやすいと思う。
$n = array(5,2,8,4);
$max = $n[0];
for($i = 0;$i < 3;$i++){
for($j = 1;$j < 4;$j++){
if($n[$i] < $n[$j]){
$max = $n[$j]
}
}
}
echo $max;
整数に関するアルゴリズム
整数に関するアルゴリズムの中から、最大公約数を求めるユークリッドの互除法と素数を求めるエネステネスのふるい、素因数分解のアルゴリズムを見ていこう。
ユークリッドの互除法
最大公約数を求めるアルゴリズム。
2つの整数があって、両方の数字を割り切れる最大の数字を最大公約数って言うんだっけ。
これもコードで見ていこう。
例として、128と72の最大公約数を見ていくか。
$m = 128;
$n = 72;
//数字の定義
$d = 1;
//最大公約数を求めるのに必要な変数
while($d = 0){
$d = $m % $n;
$m = $n
$n = $d
}
//最大公約数の算出
echo $n;
エネステネスのふるい
素数を求めるアルゴリズム。
1とその数字以外では割り切れない数が素数。
これは覚えている。
やり方は配列を用意して、素数以外を減らしていくらしい。
言葉での説明は難しいから、コードで考えていこう。
今回は10の素数を求めていく。
$a = 10;
//素数を求めたい数字
$b = $a + 1;
//N+1の定義
$data = array;
$result = array;
//配列の初期化
$m = 2;
$n = 0;
//添え字の定義
for($i = 0;$i < $b;$i++){
$data[$i] = 1;
};
//配列dataに1を格納
$data[0] = 0;
$data[1] = 0;
//素数でない数の排除
while($data[$m] == 1){
$i = $m * 2;
while($i < $a){
$data[$i] = 0;
$i += $m;
};
$result[$n] = $m;
$n++;
$m++;
if($m > $a){
echo $result;
break;
}
}
簡単に言えば素数が添え字だったら、配列resultに格納していくってことかな。
素因数分解のアルゴリズム
素因数分解は、ある数を算出するのにその数の素数をかけていくんだっけ。
上のエラトステネスのふるいを使えば、できるんだろうけど、もっと良い方法があるらしい。
名前は付けられていないみたい。
とりあえず流れをコードで見ていこう。
じゃあ、45を素因数分解していくか。
$n = 45;
$m = $n;
$i = 0;
$pf = array;
while($m !== 1){
$m--;
while($n % $m == 0) {
$m--;
};
$d = $n / $m;
while($n % $d == 0){
$pf[$i] = $d;
$i++;
$n = $n /$d;
};
$m = $n;
}
echo $pf;
エラトステネスのふるいは自信がないから、図式を見たい人はここを参照したほうが良いかも。
サーチアルゴリズム
各アルゴリズムの中でもサーチアルゴリズムは初歩中の初歩。
サーチアルゴリズムは、リニアサーチとバイナリサーチの大きく2つに分けられるそう。
これもそれぞれ見ていくか。
リニアサーチ(線形探索)
配列の最初から最後まで、見つけたい数字がどこにあるのかを順番に探していく
アルゴリズム。
見つかるまで探していく。
これ以上の説明はないよね。
コードを打つのは簡単そうだけど、データの数が多いと時間かかりそうだな…。
バイナリサーチ
配列の真ん中を見て、その数が探したい数よりも大きいか、小さいかを見て、ないとわかった片方を対象から外していく探し方。
つまり、8個の配列があったら、8→4→2という風に半分ずつ探せる。
これなら、データが多くてもリニアサーチよりも短い時間で終わらせられそう。
でも、リストが整列されている必要性があるから、その時間も考慮しないとね。
ソートアルゴリズム
次にソートアルゴリズムを見ていくか。
まぁ、いくつかは作った? 調べた?ことはあるから、気軽に見ていくか。
バブルソート
左右を比較して、値を交換していくソート。
1と2、1と3、１と4という風に比較をしていくやり方を繰り返していって、最後の1つ前まできたら終了。
PHPなら二重ループさせればスグできるね。
でも、初心者がやるからであって、扱うデータが多くなれば、時間もかかってくるか…。
簡単だけど使える場面は限られそう…。
選択ソート
配列の最小値や最大値を探して、交換をしていくソート。
昇順だったら、大きい要素をどんどん左側にしていく。
バブルソートに比べれば時間は短いだろうけど、これもデータが多くなれば時間がかかりそうだね。
挿入ソート
最初に先頭の2つの要素を取り出して比較。
3つ目からは2つの要素の中の適切な場所に入れていく。
上の2つは交換していたけど、これは取り出して入れるイメージ。
気を付けることとは、配列の状態で時間が変わる事かな。
ある程度まとまっていればスグに終わるんだろうけど、ばらばらだったら時間がかかりそう。
でも、扱いやすそうだし、どういう構文になるのか考えてみようっと。
シェルソート
図を見てもわかりにくいな…。
なんというか、一気に挿入ソートをする感覚。
早いのはわかるけれど、どういう構文になるのか想像がつかんな…
バケットソート
一定の範囲の配列(バケット)を設けて、その値と一致する添え字を入れていくソート。
これはシンプルの一言に尽きるな。
交換とかしないで、ただ入れるだもの。
ただ、容量はすごいことになりそう。
早いんだろうけど、バブルソートや選択ソートと同じ扱い方だね。
マージソート
データを2つの要素で比較できるまで分割して、それぞれを比較していくソート。
たぶん図を見たほうが早いから、こちらをどうぞ。
クイックソート
軸となる要素を決めて、それ以上の数字とそれ以下の数字に分割。
分割した要素の中でも軸となる要素を決めて分割。
交換する必要があれば交換。
これがクイックソート。
確かに今までの処理とは違って、交換する回数とか容量は少なそう。
作るのが難しいらしいから、今度Hackerrankに挑戦して、慣らしていくか。
オーダー記法
そのアルゴリズムの計算にかかる時間を表す表記。
以下に代表的なオーダーをまとめてみた。
O(n) 命令数=データ数
O(1) 命令数=データ数
O(n*n) バブルソート
O(log n) 二分探索
O(nlog n) クイックソート
まとめ
今回はアルゴリズムを勉強しました!!
知識だけじゃなくて、実際に使えるように引き続き勉強していこう!!