アルゴリズムの基礎 分析と疑似コード

#アルゴリズムとは
アルゴリズムは有効な入力に対して、計算能力によって求められた結果を有限な時間のうちに出力することができる、定義の明確な一連の手順のことです。それはつまり有効なアルゴリズムはどのプログラミング言語においても再現することができますし、逆にアルゴリズムを実際の計算機で再現することをプログラミングということもできるわけです。

##擬似コード
擬似コードはプログラミング言語ごとの特性などを無視して普遍的な理解を共有するためのものでアルゴリズムを抽象化するものです。正しく書かれた有効な擬似コードはどの言語においても再現できます。

###擬似コードの記法
擬似コードの記法は様々あり、これは一例です。

記号	意味
V	variable 変数
E	Expression 式
B	Boolean 真偽
N	Integer Valued Statement 実数値を持つ式
S	Statement 文
P	Procedure 戻り値のない一連の手順
x	Parameter 宣言された変数
<-	Assignment 代入
A[i]	Array 配列

###簡単な使用例

//計算
(x + y) * 2
//条件分岐
if B S else T
//　反復
do S while B
// forを用いた反復
for v <- n to m do S

###アルゴリズムを擬似コードで書く
例として、与えられた値の出現回数を数えるコードを書いてみましょう

ALGORITHM CountSameNum(A[0..n-1], p)
count <- 0
for i <- 0 to n - 1 do
 if A[i] == p
   count <- count + 1
return count

##アルゴリズムの分析と効率性

多くの場合アルゴリズムは多くのデータ入力があるため計算能力とその効率の分析はとても重要です
アルゴリズムの効率は二種類あります

• 時間的効率
• 空間的効率

時間的効率は計算にかかる時間における効率性で入力量に対しての経過時間を分析するものです
それにたいして空間的効率は入力量が記録機器において占める量を分析するものです

擬似コードにおける時間的効率は計算処理が行われる単位にコードを分割してそれを計上します

ALGORITHM CountSameNum(A[0..n-1], p)
count <- 0  C1
for i <- 0 to n - 1 do
 if A[i] == p C2
   count <- count + 1  C3
return count C4

$T(n) = c1+(c2+c3)(n-1)+c4 $

もちろん擬似コードをプログラミング言語に落とし込んで処理時間を計算することができますが、それは実行する計算機の影響をうけます

using System;

class Program {
    static void Main(string[] args) {
        var sw = new System.Diagnostics.Stopwatch();
        int[] sampleArray = new int[8]{1,2,3,4,1,2,3,4};
        int target = 1;
        sw.Start();
        int result = CountSameNum(sampleArray, target);
        sw.Stop();
        Console.WriteLine("result is " + result + " it took " + sw.ElapsedMilliseconds + " milliseconds");
    }
    static int CountSameNum(int[] arr, int target){
      int count = 0;
      for(int i = 0; i < arr.Length; i++){
        if(arr[i] == target){
          count = count + 1;
        }
      }
      return count;
    }
}

##その他C#で書いたアルゴリズム

2進数から10進数へ

    class Program
    {
        static void Main(string[] args)
        {
            string binaryValue = Console.ReadLine();
            Console.WriteLine(ConvertBinaryToDecimal(binaryValue));
        }
        static int ConvertBinaryToDecimal(string binar)
        {
            char[] binaryArray = binar.ToCharArray();
            Array.Reverse(binaryArray);

            int result = 0;
            for (int i = 0; i < binaryArray.Length; i++)
            {
                int binaryCharToInt = binaryArray[i] - '0';
                result += (binaryCharToInt * ((int)Math.Pow(2, i)));
            }
            return result;
        }
    }

配列の2つの要素の最小距離を求める

        static int MinimumDistance(int[] IntList)
        {
            int dmin = int.MaxValue;
            for(int i = 0; i < IntList.Length; i++)
            {
                for(int j = 0; j < IntList.Length; j++)
                {
                    if(j != i && Math.Abs(IntList[i] - IntList[j]) < dmin)
                    {
                        dmin = Math.Abs(IntList[i] - IntList[j]);
                    }
                }
            }
            return dmin;
        }

##2つのアルゴリズムの分析手法

アルゴリズムを分析するということはアルゴリズムの効率を求めることで、その手法は主に2つあります。

• 実証的分析(Empirical Analysis)
• 理論的分析(Theoretical Analysis)

###理論的分析の手順

1. 入力の大きさに関わる変数の特徴を決定する
2. アルゴリズムの基本的な関数を定義する
3. 最悪のケースの場合に必要な命令の実行回数を算出する式を設定する
4. 実行回数から実行時間を算出する。このとき結果はそれと等しい方程式か、極限まで変数を飛ばしたランダウ記号を用いた漸近記法になる

####1. 入力の大きさ
入力の大きさは用いられたデータ構造によります。複合的なデータ構造が用いられている場合は要素の数を数えます。離散数学のグラフ理論においてみれば辺や接点を数えます。そのため変数が一つでない場合も多々あります。

####2. 基本的な関数
基本的な関数というのはアルゴリズムにおいて総計算時間に最も影響を与える命令のことです。ソートにおける大小の比較、検索における一致の真偽、などなどアルゴリズムによっては一つでない場合もあります。

####例

以下の、配列における最大値と最小値を求めるアルゴリズムがあるとして

ALGORITHM GetMaxAndMin(A[0..n-1], Max, Min)
// 配列の最初の値を初期値として代入する
Max <- A[0]
Min <- A[0]
for i <- 0 to n -1 do
  if A[i] > Max
    Max <- A[i]
  else
   if A[i] < Min
    Min <- A[i]

このケースでの入力の大きさは配列Aの長さnであり、基本的な関数は最大比較と最小比較の2つあることになり、その基本的な関数は双方ともに同じ反復の中で行われるということが定義できます。

####3.最悪のケース

このアルゴリズムにおいての最悪のケースは配列の最初の要素がすでに最大の値だった場合です。その場合2つ目の最小比較がすべての反復で行われるからです。逆に通常のケースは最小比較が行われる回数とそうでない回数が等しい場合です。

{}C_{worst}(n) = \sum_{i=1}^{n-1}2 = 2\sum_{i-1}^{n-1}1 = 2(n - 1 ) = 2n-2  

####漸近記法

あるクラス$O(g(n))$が$c\times g(n)$の場合あらゆる関数に対して上界であるとき、関数$f(n)$がクラス$O(g(n))$に含まれていて、そのグラフが$cg(n)$に最も近い場合それが最悪のケースとなります。
漸近記法を用いたMaxMinアルゴリズムの効率性は以下のように書くことができます。

{}C_{worst}(n) = 2n-2 \in O(n)

たとえば単なる反復のみのアルゴリズム、ただ配列の要素をすべて足すだけなどのものの場合、$O(n)$に含まれていることが想定できます。
もし反復の中にさらに反復があり、それが比較を用いるなど複雑な場合は記述計算が必要になりますが、基本的には内包されている関数から外包の関数へと分析していきます。$O(n) \in O(n^2)$
またif elseの分岐においてはifの方の関数が$O(n)$で、elseの方が$O(m)$の場合、それを外包する反復のアルゴリズムの最悪のケースは$O(Max(n, m))$になります。

###実証的分析の手順

現実の実行環境ではメモリやCPUの問題で予測とは違う動きをすることは実にありえます。コンパイラの仕様によっては予測より早くなることも珍しいですがありえることですので、実証的な分析もぜひ行いたいところです。

1. 実証実験の目的を理解する
2. 効率性の測定基準と測定単位を設定する
3. 入力サンプルを決定する
4. 実験用にアルゴリズムをプログラムに落とし込む
5. 入力サンプルを用意する
6. 入力サンプルを用いてアルゴリズムを走らせ、データを収集する
7. そのデータを分析する

####1. 実証実験の目的を理解する
実証的なアプローチには様々な目的を設定することができます。

• 理論的手法の正確性の確認
• 同じ目的の、構造の異なるアルゴリズムの比較
• とある物理的条件下での効率性の検証
• etc...

####2. 効率性の測定基準と測定単位を設定する
主に2つの測定基準が考えられます。

1. アルゴリズムの基本的な関数が何度行われたか
2. アルゴリズムの実行にかかった時間

####3.入力サンプルの決定
論理的分析と同じように入力される変数のサイズと傾向を決定し、基本的な関数を定義します。

####4.実験用にアルゴリズムをプログラムに落とし込む
まず言語を決定し、アルゴリズムをもとにプログラムを作成します。
プログラムの挙動が擬似コード通りになっているかテストを忘れないのが肝要です。
また、経過時間測定用のコードと、基本的な関数を数えるコードは別々で組まれるべきです。
基本的な関数を数えるためのカウンターは適切な位置で宣言されなければなりませんし、それは基本的な関数の数だけ用意しなければなりません。
また、時間測定ようのコードは基本的な関数が実行される直前にタイマーが宣言され実行終了直後と比較されなければなりません。

####5. 入力サンプルを用意する

サンプルの入力されるサイズ、変数の値の範囲、関数の実行回数などを考慮して作成しなければなりませんし、プログラムでランダムな入力データを作成する必要があります。

####6. プログラムを実行しデータを収集する

サンプルデータによるアルゴリズムの実行結果を記録します。
基本的な関数の実行回数や、経過時間の平均を計算します。

####7. 収集したデータを分析する

結果は表やプロットとしてわかりやすく可視化するのが理想的で、特に散分図プロットとして表されれば、漸近線をにゅうりょくして比較するのが容易です。