ホーム » スタッフ » 斉藤徹 » 再帰方程式+動的メモリ管理

2005年5月
« 4月   6月 »
1234567
891011121314
15161718192021
22232425262728
293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

再帰方程式+動的メモリ管理

マージソートの処理速度

再帰方程式の説明の最後として、ソート処理の速度見積りを示す。 クイックソートの説明だと、微妙な所が説明が判りにくいので、 例年通りマージソートの例にて、O( N log N ) を説明。

処理の内容より、
T(1) = Ta
T(N) = Tb + 2*T(N/2) + N*Tc
再帰と同じ代入を繰り返すと、
T(1) = Ta
T(2) = Tb + 2*T(1) + 2*Tc
T(4) = Tb + 2*T(2) + 4*Tc
:
T(2^m) = Tb*(2^m-1) + 2^m * Ta + m * 2^m * Tc
よって、O( N log N )

動的なメモリ

処理速度の見積りの次のプログラム評価指針としてのメモリの使用量の説明。 再帰呼出のプログラム例から、局所変数は 『最後に出現した変数から不要となる』特徴を持っていることを紹介し、 こういったデータの保存には Stack(Last In First Out)が使えることを示す。 例として、push,pop のコードを示し、fact(階乗)のコードを push,pop を 用いて記述する。

Stackのコードも示したため、対比的な事例ということで リングバッファのコードを示し待ち行列(First In First Out)の説明を行う。

動的なメモリの説明として、授業最後に malloc,free の例を示す。 動的に配列サイズを与えるプログラム例にて説明を行う。 詳しい説明は来週に行う必要あり。