2003-04-18
_ ソフ開
探索法
・線形探索法
先頭から順番に探索
平均探索回数 n/2回
最大探索回数 n回
・2分探索法
探索する配列を半分に限定しながら探索
平均探索回数 log2(n)回
最大探索回数 log2(n)+1回
_ 整列アルゴリズム
・バブルソート
隣どおしを順次比較していく方法
n^2
・選択ソート
最大値のデータを探す方法
n^2
・挿入ソート
整列済みの列にデータを挿入していく方法
n^2
・マージソート
分割された配列を合併しながら整列していく方法
nlog2(n)
・ヒープソート
ヒープの特性を生かした整列方法
nlog2(n)
・シェルソート
挿入ソートを改良したもの
nlog2(n)
・クイックソート
データの中から基準となる軸を決め、軸より大きければ左、
小さければ右に集める
nlog2(n) 最悪の場合はn^2
概略だけ。あんまり深くやる必要はないだろと、勝手に予想。
_ 待ち行列の公式
平均到着率(λ):単位時間当たりの平均到着数(件/時間) 何件来るか
平均処理率(μ):単位時間当たりの平均処理数(件/時間) 何件処理できるか
利用率(ρ):サービス窓口が処理中である確率
ρ=λ/μ
(1時間で100件処理できる窓口に、1時間で50件到着する、このとき利用率は0.5となる)
平均処理時間、平均サービス時間(Ts)
Ts=1/μ (時間/件)
平均待ち時間(Tq)
Tq=(ρ/1-ρ)*Ts
応答時間(Tw)
Tw=Ts+Tq
もうね丸暗記。難しい問題がでると正直、歯が立たないよ。
_ 今日の東海道線
今までで一番込んでた。
19時23分東京発に乗ったんだが、乗った車両が悪かったかな。
おばちゃんなんて悲鳴を上げてたし。
オレは2人掛けの席に座ってんたけど、
立ってる人がもうオレの上に乗りかかってきて押しつぶされそうだった。
ボックス席に座らないと駄目だね。あっちはかなり余裕があった。
今度からボックス席に座ろう。
あの込み方は死人出てもおかしくない。
子供や体の弱い人は絶対に乗っちゃ駄目だね。
東海道線は駅の間隔が結構長いから逃げられないよ。