『アルゴリズム導論』読書ノート(一)——挿入ソートと循環不変式

初めて「アルゴリズム導論」を学び、読書の順番に心得を記録した.
——————————————————————————————
挿入ソートの簡単なC++実装:

#include <iostream>
using namespace std;

void insert_Sort(int a[], int length);

int main()
{
	const int n = 10;
	int a[n] = {1,3,5,7,9,0,2,4,6,8};
	insert_Sort(a, n);
	for(int i = 0; i < n; i++)
	{
		cout << a[i] << "\t";
	}
	cout << endl;
	return 0;
}

void insert_Sort(int a[], int length)
{
	for(int i = 1; i < length; i++)
	{
		int temp = a[i];
		int j = i - 1;
		while(j > -1 && a[j] > temp)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = temp;
	}
}

循環不変:
初期化:ループの最初の反復の前に、それは真です.
保持:ループの反復が真の場合、次回の反復の前に真の場合.
終了:サイクル終了時に、アルゴリズムが正しいことを証明するのに役立つ不変式を提供します.
挿入ソートには、ループ不変形が適用されます.
初期化:ループが開始される前(i=1の場合)、秩序化されたグループはa[0]の1つしかないので、それは真です.
保持:現在の反復が真の場合、今回の反復は、a[0]からa[i-1]にa[j]を挿入する適切な位置であり、a[0]からa[i]が秩序化されたグループとなり、次の反復まで真のままとなる.
終了:外側のforループの終了条件は、i=length、すなわち配列長を超えるダウンスケールである.ループ反復iごとに1が増加するので、このときi=lengthは、ループ不変式でiをlengthに置き換え、サブ配列a[0..length−1]がa[0..length−1]に元の要素からなるが、順序付けされている.サブ配列a[0..length-1]は配列全体であるため、配列全体がソートされ、アルゴリズムが正しい.
ぶんせきアルゴリズム
最も関心のある:時間を計算します.
使用モデル:RAM、シングルコア、シーケンス実行、同時実行なし
データ型:整数、浮動小数点、精度にあまり関心がありません
グレー領域:指数演算などの命令はリストされていません.
メモリレベル:一般的には関心がありませんが、特定のアルゴリズムの影響は大きいです.ほとんどの場合、考慮しなくてもパフォーマンスを予測できます.
数学ツール:数学、確率論、代数テクニックなどを組み合わせる
説明方法:規模の関数を入力
入力規模:アルゴリズムごとに入力規模の記述が異なり、指定が必要
実行時間:「ステップ」で記述し、ステップごとの所要時間は定数でciで表す
挿入ソートアルゴリズムの解析
ソートの実行時間の挿入
insert_Sort
代償
回数
for(int i = 1; i < length; i++)
c1
n
    int temp = a[i];
c2
n-1
    int j = i - 1;
c3
n-1
    while(j > -1 && a[j] > temp)
c4
t2+...+tn
        a[j + 1] = a[j];
c5
t2-1+...tn-1
        j--;
c6
t2-1+...tn-1
    a[j + 1] = temp;
c7
n-1
挿入ソートの実行時間は、コスト*回数の合計です.
回数から,入力規模が決定されたとしても,回数は入力によって変化する可能性がある.
挿入ソートの場合、入力が順序付けされている場合、所要時間はnの線形関数、すなわちTn=an+bである
入力が完全に逆シーケンスである場合、所要時間はnの二次関数、すなわちTn=an^2+bn+cである
最悪状況と平均状況分析
なぜ最悪の状況を分析するのか:
1.最悪の場合、上界が与えられる.
2.いくつかのアルゴリズムでは、最悪の場合によく発生します.
3.平均的な状況は最悪の状況と同じように悪いことが多い.
成長レベル
式の最も重要な項目のみを考慮し、高次を保持し、低次を無視し、項係数を無視します.
このように、挿入アルゴリズムの成長レベルは次のとおりです.Θ(n^2)