アルゴリズムの評価基準

概要

アルゴリズムの評価基準は以下の三つに分けられる。

• 可読性
  • コードが読みやすいか、分かりやすいか
• 効率性
  • どのくらいメモリを使うか、時間を使用するか
• 正確性
  • 正しい結果を得られるか

可読性

可読性とは、コードがどのくらい読みやすいか、分かりやすいかを示すものである。
以下に比較を載せる。

//可読性の低いコード
void a(){
int e;
		for (e = 1; e <= 10, e++)
		printf("%d",e * 2);
}
 
//可読性の高いコード
void sumEvenNumber(){
	int evenNum = 2;
	int count = 0;
	
	for(count = 0; count < 10; count++){
		printf("%d",evenNum);
		evenNum *= 2;
	}
}

Check

• 処理を基本制御構造とその組み合わせで表現する⇒構造化プログラミング
• 字下げ(インデント)や空行のルールを統一する。
• 変数名や関数名を工夫する。

正確性

正確性とは、アルゴリズムが正しい結果を得ることが出来るかを表すものである。また、プログラムの処理手順が正しいかが表している。

まずは、110の総和を求めるコードを記述するとする。
110の総和は実際は55である。

void S-1(){
	int num, sum;
	
	sum = 0;
	for(num = 1; num < 10; num++){
		sum += num;
	}
	
	printf("%d",sum);
}

しかし、このコードは実行結果では44となる。

この原因はforの条件式で<となっているためである。正しくは<=である。

$(\frac{1}{3}{)}^5$を求めるアルゴリズム

以下のコードは$(\frac{1}{3}{)}^5$を求めるものである。

void s1(){
	float num;
	int cnt;
	
	num = 0;
	for(cnt = 0; cnt < 5; cnt++){
		num = num * 1/3;	
	}
	
	printf("%f",num);
}

$$\begin{array}{r}実行結果\\ 0.004115226213\\ \\ 正解\\ 0.004115226337\end{array}$$

これの原因は誤差である。
コンピュータではすべての数値を二進数で表すが、実数の$\frac{1}{3}$をただし良く表現できない。

効率性

効率性とは、アルゴリズムの効率)(計算量)の良さを表す。

• 計算量
  • 時間計算量：アルゴリズムの処理時間
  • 空間計算量：メモリの使用領域
• 一般的に時間計算量を使用
  • 時間計算量の上限は$O$(オーダ)表記で表す。
• 時間計算量の評価方法
  • 実行時間による評価
  • 命令の実行回数による評価

実行時間による評価

#include<stdio.h>
#include<sys/time.h>
 
int main(void){
	int N = 5;
	int i, j, k , sum;
	struct timeval, start, end;
	
	gettimeofday(start, NULL);//開始時間を記録
	
	for(i = 0; i < N; i++){
		for(j = 0; j < N; j++){
			for(k = 0; k < N; k++){
				sum += i * j * k;
			}
		}		
	}
	
	gettimeodgay(end, NULL);//終了時間を記録
	
	//実行時間を計算
	printf("%d(マイクロ秒)\n",end.tv_usec - start.tv_usec);
	
	return 0;
}

N	時間計算量(マイクロ秒)
5	1
10	4
15	16
20	31
25	56
30	121
35	217
40	284
45	319
50	692

Check

1. Nが大きくなると命令の実行回数が大きくなる。
2. 実行時間は、命令の実行回数に比例する。

命令の実行回数による評価

• 実行する命令の数が多ければ多いほど、実行時間が長くなる。
• 命令の実行回数の計算
  • 各命令が何回実行されるかを計算する
  • 全ての命令の実行回数の総和を計算する。

オーダ($O$)表記

最も影響を与える部分の計算量を表す表記法

• 一定
• $n$に比例
• $n^2$
• $n$の対数($\log n$)に比例する

void P-1(){
	int n, m, num, sa;
	scanf("%d",&n);
	scanf("%d",&m);
	
	if(n >= m) sa = n - m;
	else sa = m - n;
	
	printf("nとmの差%dです",sa);
}

プログラム	命令の実行回数	最も影響を与える部分	オーダ表記
P-1	$4$		$o(O)$
4	$1+4n$		$o(n)$
P-3	$1+n+n^2$		$o(n^2)$