毎月アルゴリズム – 第3回 –

はじめに

こんにちは。よっしーです。
毎月アルゴリズムを考えていくブログの第3回目です。
前回はデータ構造に関して考えた後にソートのアルゴリズムを紹介しました。
データ構造の話が大半を占めており、メインがデータ構造のブログになってしまいました。笑
アルゴリズムを考える上で、データ構造は重要なものですので、避けて通れないので力を入れてお話しました。
今回もデータ構造に関して少しお話してその後、アルゴリズムを紹介したいと思います。
それでは早速考えていきましょう。

今回もアルゴリズムを考える前に

データ構造を考えようその2

前回同様データ構造に関してお話したいと思います。
今回はスタック、キューに関して解説します。
前回と同様にデータ構造は文章での説明より図の説明のほうが分かりやすいので、少し図が多くなってしまいます。
退屈かもしれませんが見ていただけますと幸いです。

スタック

スタックはデータを一列に並べるのですが、最後に追加したデータからしか取り出せないという特徴があります。
よく、積み上げられた本に例えられることが多いです。
新しい本を本の上に積みますが、真ん中の本を取りたいときは一番上の本からどけていかないと取れないと言うケースに似ています。
後から入れたものを先に出す、「後入れ先出し」の仕組みを「Last In First Out」、略して「LIFO」と呼びます。
なんかかっこいいですね笑

積み上げていく操作をpushと呼び、要素を取り出す操作をpopと呼びます。
また、リストの先頭をtop、終端をbottomと呼びます。

追加、削除は以下のようになります。

追加

削除

一見すると使いづらいなと思われるこのデータ構造ですが以下の利点があります。

スタックの実装によるが、一般的に、スタックトップのインデックスあるいはポインタ（スタックポインタと呼ぶ）を増減するだけで、配列内のデータを移動する必要はなく、高速に処理できる
利用者はpush, popのみしか操作をすることがないので、利用時のデータの中身がどうとか考えずに操作が可能(制約があることで操作が容易になる)

利用例としてはなにかの履歴に使われることがあります。
例えば、Webブラウザの遷移履歴等を積んでおくことができます。
また、テキストエディタで操作コマンドをスタックに積んでおくことでUndo機能を実装できたりすることができます。

まとめ

スタックはデータを一列に並べ、先頭にデータを追加していくデータ構造
データへのアクセスはリストの先頭にのみ制限されている(追加も削除も)
データの追加、削除するスピードは速い(push, popともにオーダーは $O(1)$ )

キュー

キューはスタックと同様にデータを一列に並べるのですが、スタックの追加する側と削除する側が反対です。
初めに追加したものからしかデータを取り出せないという特徴があります。
スタックとは逆で、席に入れたものを先に出す、「先入れ先出し」の仕組みを「First In First Out」、略して「FIFO」と呼びます。

キューに詰めていく操作をenqueueと呼び、取り出す操作をdequeueと呼びます

追加、削除は以下のようになります。

追加

削除

同じく制約があるキューですが、スタックと同じような利点があります。
スタックと違うのは、データの取り出し順番だけですが、キューの利用例は早いもの勝ちのジョブをさばくようなときに使ったりします。
例えば、大繁盛のレストランのWebサイト等で、予約がいっぱいになっているときのキャンセル待ちの人のリストを管理したいといったときに利用できるかもしれません。

まとめ

キューはデータを一列に並べ、末尾にデータを追加していくデータ構造
データへのアクセスはリストの先頭/末尾にのみ制限されている
データの追加、削除するスピードは速い(enqueue, dequeueともにオーダーは $O(1)$ )

オーダーに関して

以前オーダーに関しては $O(n)$ 等のランダウ記号で表せるという話をしました。
例えば、
$4n^3 + 2n^2 + 1 = O(n^3)$
と表せるという話をしました。
当然間違ってはないのですが、厳密には説明が足りていません(一気に説明すると混乱すると思いましたので)。
計算量理論において、計算量の評価は以下に分類されます。

ビッグオー

今まで利用していた $O(n)$ 等のことです。
大体最高次数の係数を外したものを書いておいてください的な説明だったと思いますが、本来意味は少し違います。
$O$ を使う意味合いは、ざっくり言うと早くてもその関数と同じぐらいのスピードで発散するよ(これを上界といいます)という意味です。

厳密な定義を記載しますと、少し数学的な話になるんですが

ある $n$ に関する関数 $f(n)$ , $g(n)$ を考えたとき、
ある $n_0 ,c$ が存在して $n > n_0$ なら $f(n) \leqq cg(n)$ が成り立つ場合、
$f(n) = O(g(n))$ と表記する。

これが厳密なビッグオーの定義です。
訳分かんねぇと思うと思いますが、例を具体的に考えてみましょう。

$4n^3 + 2n^2 + 1 = O(n^3)$ ・・・ (1)
ですと伝えたんですが、これが本当に合ってるか考えてみましょう。
そうしますと定義に合いそうな感じで一旦以下と置いてみましょう。

$f(n) = 4n^3 + 2n^2 + 1$
$g(n) = n^3$

定義にある “ある $n_0 ,c$ が存在して $n > n_0$ なら” みたいな文言が意味不明だと思いますが、
とても簡単に噛み砕くと、 $g(n)$ を定数倍したような関数はどっかのタイミングから $f(n)$ より大きくなるよってことが言いたいだけです。

例えば、
$f(n)$ vs $5g(n)$ を考えてみたいと思います。
適当に大きな値を考えてみたとき、例えば $n=1000$ くらいを考えてみたとき、

$f(1000) = 4 \times 1000^3 + 2 \times 1000^2 + 1 = 4,002,000,001$
$5g(1000) = 5 \times 1000^3 = 5,000,000,000$

なので $f(n)$ は $5g(n)$ に負けてます。
そして1000より大きい数字で金輪際 $f(n)$ は $5g(n)$ に勝つことはありません。
そのため、 $n>1000$ のとき $4n^3 + 2n^2 + 1 \leqq 5 n^3$
ということになりますね。
このとき $n_0 = 1000, c =5$ をチョイスして定義を満たしてるので
$f(n) = O(g(n))$ つまり(1)を満たしてるねってことが言えます。
$n_0 = 1000, c =5$ をチョイスしましたが、もっと選べる数字はいっぱいあります。
$n_0$ を1000と置きましたが、どっかの瞬間から超えてたら良いのでもっと緩く考えてもOKです(10000とか1億とかでも大丈夫です)。
$c$ もぶっちゃけ4より大きい数ならいずれ勝ちます。
以下の図を見ていただけますと一目瞭然ですね。
赤い線で書いた関数(今回の $f(n)$ )よりも大きい関数が一つでもあれば $O$ のオーダーとしてもOKです(ここでは $5n^3$ より大きい数字では超えています)。

ここで、じゃあ $10000n^2$ と比べたらどうなるの？とか、 $n^4$ ならどうなるの？といったことも考えられますね。
ちょっと考えてみます。

$4n^3 + 2n^2 + 1$ vs $10000n^2$

$4n^3 + 2n^2 + 1$ vs $n^4$

$10000n^2$ は初めは勝っていますが、途中から抜かされてしまいそこから追いつくことはできません。
$n^4$ は圧勝ですね。
なお、 $n^4$ はある点以降数字が大きくなるので、定義に則っていますよね？
そのため、以下のように書くことも可能です。

$4n^3 + 2n^2 + 1 = O(n^4)$

しかし、 $O(n^3)$ と比べると制限がゆるいので $O(n^3)$ と $O(n^4)$ では $O(n^3)$ のほうがより価値があると言えます。

ビッグオメガ

ビッグオーが上界を表しているなら、下界(遅くてもその関数と同じぐらいのスピードで発散するもの)もあるのではないかと推測することができます。
実際に存在しており、その記号を $\Omega$ で表します。
定義は以下です。

ある $n$ に関する関数 $f(n)$ , $g(n)$ を考えたとき、
ある $n_0, c$ が存在して $n > n_0$ なら $f(n) \geqq cg(n)$ が成り立つ場合、
$f(n) = \Omega(g(n))$ と表記する。

上記はビッグオーと反対で $g(n)$ を定数倍したような関数はどっかのタイミングから $f(n)$ より小さくなるよってことが言いたいだけです。
なので、説明は省略しますね。

ビッグシータ

今まで上界と下界を考えてきましたが、上界と下界が一致することがあります。
それを分かりやすい記号で $\Theta$ と置きます。
度々自分は $O$ (ビッグオー)を用いてきましたが、アルゴリズムの世界において、よくビッグシータのことをビッグオーと表現することが多いので注意してください。
定義は以下です。

ある $n$ に関する関数 $f(n)$ , $g(n)$ を考えたとき、
ある $n_0, c_1, c_2$ が存在して $n > n_0$ 　なら $c_1g(n) \leqq f(n) \leqq c_2g(n)$ が成り立つ場合、
$f(n) = \Theta(g(n))$ と表記する。

少し表現を変えると
$f(n) = O(g(n))$ かつ $f(n) = \Omega(g(n))$ は $f(n) = \Theta(g(n))$ の必要十分条件ということですね。

なお、今まで例に上げてきた以下の関数は実はビッグシータで表現することができます。
$4n^3 + 2n^2 + 1 = \Theta(n^3)$

まとめ

$O$ (ビッグオー)は関数の上界を示すときに用いる記号
$\Omega$ (ビッグオメガ)は関数の下界を示すときに用いる記号
$\Theta$ (ビッグシータ)は関数の上界、下界が一致しているときに用いる記号

上記厳密な定義ができました。
今後はできるだけこの表現を正しく用いて記事を書いていけたら良いなと思います。

アルゴリズムを考えてみる

さて、今回も前置きが長くなりましたが、本日もまたまたソートに関してアルゴリズムを考えていきます。
前回は選択ソートを考えてみましたが、今回は挿入ソートです。

挿入ソート

概要

挿入ソートは数列の左側から順番にソートしていきます。左側から順に、数字を一つ取ってきてソート済みのものの適切な位置に挿入します。

処理

元データを用意する
一番左の数字をソート済みにする
まだ操作していない数字の中で一番左の数字を取り出し、操作済みになっている数字と比較していく。左の数字が大きい場合、2つの数字を入れ変える。この操作を自分より小さい数字が現れるか、数字が左端に到達するまで繰り返す
操作した数字を操作済みとする
3～4を繰り返し行う
一番右のデータ以外すべてがソート済みになったら操作を完了する

処理の上記処理

オーダー

オーダーは今回はいつもと違う書き方になってしまいます。

最悪のケースの計算量は $\Theta(n^2)$
最良のケースの計算量は $\Theta(n)$
平均の計算量は $\Theta(n^2)$

となります。
少し分かりづらいと思いますが、データの並び方によって計算量が変化すると考えていただけると分かりやすいです。
例えば、初めからソートされている数列に対しては最良の計算量が、逆順でソートされている数列に対しては最悪のケースの計算量となります。
平均ってなんぞやってところですが、すべての数字の並び方のケースの計算量を考慮してケース数で割ってあげる必要があります。

少し簡潔に書くと、
1, 2, 3という数列があった場合、数列の順番は
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
の6通りありますね。
これらをソートするには平均どれだけ計算したかを考えてあげましょう(計算間違えてたらすみません)。
(1, 2, 3) = 3 ステップ
(1, 3, 2) = 4 ステップ
(2, 1, 3) = 4 ステップ
(2, 3, 1) = 5 ステップ
(3, 1, 2) = 5 ステップ
(3, 2, 1) = 6 ステップ
となり、平均の計算量は $(3 + 4 + 4 + 5 + 5 + 6) / 6 = 27 / 6$ となります。
今、 $n=3$ のときを考えましたが、一般的な $n$ に関して考えたとき、 $n^2$ に比例しているようです。
上記のような考えで10程度({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}の数列)までの整数の組み合わせを考えてみたとき以下のようになりました。

n	平均の計算量
2	2.5
3	4.5
4	7
5	10
6	13.5
7	17.5
8	22
9	27
10	32.5

上記の近似曲線を考えてみると、 $0.25n^2 + 0.75n + a$ と近似できそうでした。
(最悪ケースが $\Theta(n^2)$ なので、 $n^3$ 以上の係数の曲線は考えていません。)

コード

例によって挿入ソートのコードを考えてみました。
コードはお馴染みのC#で書いています。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Algorithm
{
  class Program
  {
    static void Main(string[] args)
    {
      var list = new List<int>();
      
      // 1～20の数字をバラバラに配列に入れる
      for (var i = 1; i < 21; i++)
      {
        list.Add(i);
      }

      var array = list.OrderBy(x => Guid.NewGuid()).ToArray();

      Console.WriteLine("{" + string.Join(",", array) + "}");

      Console.WriteLine("{" + string.Join(",", InsertSort(array)) + "}");
    }

    public static int[] InsertSort(int[] arr)
    {
      // 初めのデータはソート済みとするため、i = 1からスタート
      for (var i = 1; i < arr.Length; i++)
      {
        for (var sort = i; sort > 0; sort--)
        {
          // 隣の数字と大小比較。左の数字のほうが小さければ抜ける
          if (arr[sort] > arr[sort - 1])
          {
            break;
          }

          var tmp = arr[sort];
          arr[sort] = arr[sort - 1];
          arr[sort - 1] = tmp;
        }
      }

      return arr;
    }
  }
}

using System;

using System.Collections.Generic;

using System.Linq;

namespace Algorithm

{

class Program

{

static void Main(string[] args)

{

var list = new List<int>();

// 1～20の数字をバラバラに配列に入れる

for (var i = 1; i < 21; i++)

{

list.Add(i);

}

var array = list.OrderBy(x => Guid.NewGuid()).ToArray();

Console.WriteLine("{" + string.Join(",", array) + "}");

Console.WriteLine("{" + string.Join(",", InsertSort(array)) + "}");

}

public static int[] InsertSort(int[] arr)

{

// 初めのデータはソート済みとするため、i = 1からスタート

for (var i = 1; i < arr.Length; i++)

{

for (var sort = i; sort > 0; sort--)

{

// 隣の数字と大小比較。左の数字のほうが小さければ抜ける

if (arr[sort] > arr[sort - 1])

{

break;

}

var tmp = arr[sort];

arr[sort] = arr[sort - 1];

arr[sort - 1] = tmp;

}

return arr;

}

おわりに

今回も前回までと同様の流れで進めていきました。
次回も同じ構成で進めていくと思いますが、よろしければ見ていただけますと幸いです！

新卒エンジニアへ送る「これ押さえておこう」リスト: Vol.1 コミュニケーション編

量子テレポーテーション

毎月アルゴリズム – 第3回 –

はじめに

今回もアルゴリズムを考える前に

データ構造を考えよう その2

スタック

追加

削除

まとめ

キュー

削除

まとめ

オーダーに関して

ビッグオー

ビッグオメガ

ビッグシータ

まとめ

アルゴリズムを考えてみる

挿入ソート

概要

処理

処理の上記処理

コード

おわりに

最近の記事

レイアウト解析

ChatGPTを用いた画像異常検知

クォータニオンと回転行列の関係

OpenCVで深層学習

OpenCVのcv::Matに関する小ネタ集

テンソルネットワークの入り口（その2）

毎月アルゴリズム – 第2回 –

毎月アルゴリズム – 第4回 –

初歩的な数学のアルゴリズムを考えてみよう

【モンテカルロ法】プログラミングで円周率を求める方法

【モンテカルロ法】ビュフォンの針の問題

毎月アルゴリズム – 第5回 –

Google Vision APIでOCR

アーカイブ

カテゴリー

データ構造を考えようその2