先週の再帰処理の時間分析ということで、ハノイの塔の処理ステップの 数学的帰納法による証明を説明する。この後、マージソートの分析とメモリ利用の効率 について説明を行った。

マージソートの分析

マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となることを示す。

また、この結果を踏まえ、 最大選択法Tm(N)のプログラムと、クイックソートO(N×logN)処理時間はTq(N) があって、 Tm(100)=1msec , Tq(100)=2msec であったとして、 データ件数N=200の時には、どちらのアルゴリズムの方が速いか？ データ何件以上で、クイックソートを採用すべきか…といった問題について説明を行う。

メモリ利用の効率

次にメモリの利用効率の話について解説する。
例えば、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。

#define MEMBER_SIZE 50
#define NAME_LENGTH 20
char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;

しかしながら、クラスに寿限無のような名前の人がいたら、20文字では足りない。 また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の寿限無ありを考慮して、5Mbyte の配列を使うのは、 明らかにメモリの利用効率が低い。

このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。

char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ;
char *name[ 50 ] = {
array+0 , array+6 , array+14 , array+23 , ...
} ;

この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。

来週は、必要に応じてメモリを確保する、mallc() + free() を解説する予定。