前ページで扱ったカードを並び替える2つの方法についてもう少しどちらがどれだけ速いかを確認してみましょう。
小さい順に並べるときの速さ
まず手順についておさらいしましょう。
①全てのカードから1番小さいカードを見つける。
②正しい場所に置く。
③全て並ぶまで①②を繰り返す。
ではそれぞれのステップでどれだけ手間がかかっているか確認してみましょう。
①は残っているカードの中で1番小さいカードの位置によって確認回数が変わります。50枚残っているとき1枚目が1番小さいかもしれませんし、49枚確認して最後が1番小さいかもしれません。ここでは期待値を考えたいので毎回真ん中に1番小さいカードがあるとして考えましょう。つまり①では残った枚数の半分だけ確認することになります。
②ではただ正しい場所に置くだけです。
つまり今回このアルゴリズムを考えるとかかる確認の回数は(100÷2)+(99÷2)+(98÷2)+…+(2÷2)です。これを計算してみると2525回となります。
では先にグループ分けするとどうでしょう。
先にグループ分けを行ってみる。
①先にグループ分けを行う。
②それぞれのグループ内で並び替えを行う。
③並び替えたグループを繋げる。
ここでは10グループに分けるとしましょう。
では①でかかる確認の回数を考えましょう。これは100枚全てをそれぞれどのグループに入るか振り分けるだけなので100回確認すれば済むでしょう。
では②でかかる確認回数はどうでしょう。1つのグループごとに先ほどの小さい順に並び替えるとします。このとき1つのグループごとに(10÷2)+(9÷2)+(8÷2)+…+(2÷2)=27回です。10グループなので270回ですね。
つまりこのアルゴリズムでは100+270=370回の確認で良いことになります。先ほどのアルゴリズムに比べて7倍近く速く終わっていますね。
計算量という考え方
アルゴリズムの速さはこのようにどれだけ計算をする必要があるかで評価します。ここでいう「どれだけ計算が必要か」という数字を計算量といいます。
計算量の重要さ
今回は100枚のカードの並び替えで7倍もの差が出ました。ですがこの差はカードの枚数が増えれば増えるほど100倍、1000倍とどんどん離れていきます。カードではイメージしにくいかもしれませんが、これが大きい会社のお客様の情報だったらどうでしょうか。5000万以上のデータがあった場合1時間で終わるか1年かけても終わらないかという差になるかもしれません。
次のページではどのように無駄を省いて速いアルゴリズムを見つけるかの話をしたいと思います。