マージソートのオーダー
マージソートの分析 マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。 こ […]
再帰処理の処理時間
再帰関数と再帰方程式 再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。 // 階乗 int fact( in […]
繰り返し処理とオーダ記法
先週に、単純繰り返し処理の時間分析をやったので、次のステップに。 2分探索法の処理時間 データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。 // 2分探索法 O(log N) […]
情報構造論ガイダンス
情報構造論のガイダンス プログラム作成でのポイント この授業で恒例の、プログラムを作る場合に何に気をつけてプログラムを作成するかを聞いてみた。今年は、以下に示す3要素をうまく答えてくれたかな。 プログラムの速度 プログラ […]
mallocとfreelist
C言語では、動的メモリ領域をどのように管理していくのか解説する。 動的メモリ領域とフリーリスト 動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却す […]
ガベージコレクタと演習(ハッシュ法)
ハッシュ法について演習ができていなかったので、前半座学(ガベージコレクタ)と後半演習(ハッシュ法) ガベージコレクタ 前回、malloc などで使用を終えたデータを free で開放する際に発生する問題について説明し、そ […]
文字をキーとするハッシュ値
前回のハッシュ法では、数値(電話番号)をキーとする検索であった。 このためハッシュ関数は、数値の不規則性の部分を取り出すだけでよかった。 それでは、文字をキーとしてデータを探す場合はどのようにすればよいか？ 文字列をキー […]
ハッシュ法
2分木なども終わって、検索処理のさらなる高速化として、 ハッシュ法を説明する。 オープンアドレス法 電話番号が記録されているのかどうかを探す処理を考えると、 最も単純な方法は、電話番号を配列の添字にする方法となる。 in […]
情報構造論はテスト返却
情報構造論は、来週不在となるので、授業時間を振り替えてテスト返却を行った。
B木の構造とデータベース
2分探索木の考え方を拡張したもので、B木がある。 B木の構造 B木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータ […]