アルゴリズム

○計算量には時間計算量と空間計算量がある。通常、アルゴリズムの評価には時間計算量が用いられることが多い。

○オーダー表記
１．n⁵
２．n²
３．3ⁿ

○最小値を求める問題
s=a[0];
for(i=1;i<n;i++){
	if(a[i]<s)	s=a[i];
}

○ポインタの復習
void add(float a,float b,float *c){
	*c=a+b;
}
main(){
	float a,b,c;
	add(a,b,&c);
}

○再起表現
ていうか、べき乗(n!)ってなんだ？どうやって求めればいいのだろうか。
ここでは一応階乗(n!)として問題を解きます。

kaijyou(int i){
	if(i==1) return 1;
	else	 return i * kaijyou(i-1);
}
void main(void){
	int x;
	scanf("%d",&x);
	printf("%d",kaijyou(x));
}

○ソート><
for(i=0;i<n-1;i++){
	min=i;
	for(j=i+1;j<n;j++)
		if(a[j]<a[min])	min=j;
	temp=a[i];
	a[i]=a[min];
	a[min]=temp;
}

○上のプログラムは小さい順に並び替えられる。

○4行目のif文の実行回数をデータ数nであらわせ、また、これをオーダー表記せよ。

(n-1)n/2
O(n²)

○{1,2,3,10,4,7,8,6,8,6,5,9}

○バブルソート
１．
for(i=n-1;i>=2;i--){
	for(j=0;j<i;j++)
		if(a[j]<a[j+1]) swap(&a[j],&a[j+1]);
}
２．データの入れ替えを行う手続きSwapを書け。

swap(double *a[j],double *a[j+1]){
	double temp;
	
	temp = *a[j];
	*a[j] = *a[j+1];
	*a[j+1] = temp;
}


○バブルソートの計算量をオーダー表記せよ。
O(n²)

○バブルソートの計算量削減
for(i=n-1;i>=2;i--){
	sentinel=0;
	for(j=0;j<i;j++)
		if(a[j]<a[j+1]){
			swap(&a[j],&a[j+1]);
			sentinel=1;
		}
	if(!sentinel) break;
}
並び替えの必要が無いとき（すでに並び替えられているとき）選択ソートよりも早く終了する。

○挿入ソート
for(i=1;i<n;i++){
	j=i; temp=a[i];
	while(a[j-1]>temp && j>0){
		a[j]=a[j-1];
		j--;
	}
	a[j]=temp;
}
変数Tempを用いている理由を述べよ。
別にTempじゃなくてもPonchoでもTentoでも可。（笑

○ヒープソート
○ダウンヒープ
down_heap(double a[],int j, int k){
	double temp;
	int i;
	temp=a[j];
	while(j<k/2){
		i=2*(j+1)-1;
		if(i<k-1 && a[i]<a[i+1]) i=i+1;
		if(temp<a[i]){
			a[j]=a[i];
			j=i;
		}
		else break;
	}
	a[j]=temp;
}

○ヒープソートの計算量をオーダー表記で示せ。
O(nlogn)

○クイックソート
quick_sort(double a[],int left,int right){
	int i;
	if(left<right){
		i=partition(a,left,right);
		quick_sort(a,left,i-1);
		quick_sort(a,i+1,right);
	}
}

○クイックソートの平均計算量をオーダー表記で示せ。
O(nlogn)

○構造体の使い方

○上を改造

○二分探索

○二分探索法の最大計算量をオーダー表記で示せ。
O(log₂n)

○ハッシュ法におけるハッシュ関数の例をあげよ。

○ハッシュ法にはチェイン法とオープンアドレス法がある。ハッシュ法においてひとつのレコード
の記憶場所をバケットという。記憶場所全体に対して実際にレコードが入っている場所の割合を
バケット使用率という。

○

○
１．
２．
３．

○
チェイン法ではバケット使用率が小さいときは計算量はO(1)だが、バケット使用率
が大きいときはO(N)である。

○
オープンアドレス法においてはハッシュ値が一致するレコードが生じた場合（これを衝突という）
再ハッシュ（Rehash）という関数を用いてハッシュ値を計算しなおして新たなバケットを割り当てる。
このような関数の一例をC言語で記述せよ。

○パターンマッチング
１．p
２．二つの文字列をｎ文字分比較する関数
３．NULL
４．O(n)

○文字列パターンマッチング
（略）
この関数を失敗関数という。また、このアルゴリズムをクヌース・モーリス・プラット法という。
パターンが”ababc”である場合この関数の値は

一致文字　0 1 2 3 4
関数値　 -1 0 0 1 2

○
（略）
ボイヤー・ムーア法という。

この方法の実行例を下図に示す。二回目以降のパターンの比較位置を図に書きこんで示せ。

storage for strings
ring          |  |
   ring       |  |
       ring   |  |
          ring|  |
              ring


○以下のグラフを隣接行列によりあらわせ

[1010]
[1011]
[0000]
[1000]

○下図で、各弧の長さが異なると仮定し、AからBへの最短距離を総当り法で求めようとする場合、何通りの経路を調べなければならないか。
（図略）

○最短経路問題を効率良く解くアルゴリズムとしてダイキストラ法がある。
このアルゴリズムの基本的な考え方は、すべての頂点を以下の三つに分類して、集合Pの要素に、
集合Tからひとつずつ繰り入れることにより、最終的に終点の頂点がPに含まれるまで繰り返す、
というものである。
集合P：始点からの最短距離が求められた頂点の集合
集合T:Pに接する（弧がのびている）頂点の集合
集合U：それ以外

ここで、集合Tの頂点のうちどのような条件を満たすものが、集合Pに繰り入れられるのか述べよ。
たぶん始点にもっとも近い頂点だと思う。

○ダイキストラ法の最大計算量をオーダー表記にて示せ
分からん。眠い。

間違っていても知らんよ？
間違い発見者は即作者まで通報してください。
Last Update : 1999/01/31