アルゴリズム過去問
気になった問題をちょこちょこ書こうっと。
2.n個の整数から、最大値と最小値を求めるアルゴリズムを設計せよ。(ヒント:分割統治)
整数どうしの比較はたかだか3/2･n回
比較回数に注意して解いてみる。
メンドイので配列a[1]〜a[n]グローバルでお願いします。
void max_min(int n, int i, int* max, int* min){
n=1のとき、最大最小ともに、a[i] 比較数0回
n=2のとき、a[i]>a[i+1] で、大きいほう最大、小さいほう最小
比較数1回それ以外。
int max1,max2,min1,min2;
max_min(n/2,i,&max1,&min1);
max_min(n/2,i+n/2+1,&max2,&min2);
max1とmax2の大きいほうを最大、
min1とmin2の小さいほうを最小とする。 比較数2回
}
こんな感じ。
比較回数を計算してみる。(ほぼ教科書の写し)
簡略化のため、n=2^kとすると、結局
T(n) = 2T(n/2) + 2
= 2+2^2+.....+2^(k-1)+2^(k-1)
となる。最後の2^(k-1)はn=2のとき1回しか比較しないから･･･汗。
で、最後の項以外等比級数だから、
T(n) = 2(1-2^k)/(1-2)+2^(k-1)
= 2^k-2+2^(k-1)
= (1+1/2)2^k-2
= 3/2･2^k -2
= 3/2･n-2
で、確かに3/2･n回以下だねと。こんなんかなぁ。。。なんかなぁ。
5.k番目に小さな要素をO(n)で見つける。
考え方は、
- n==1ならその要素で決定。
それ以外
