Entries from 2019-06-01 to 1 month
counting sortは最速の探索アルゴリズムの一つ。 time complexityはO(n+k) 配列は合計で3つ使用する。 探索対象の配列A、indexを記録しておくための配列C、出力用の配列Bの3つ。 配列Cでは、配列Aの中で出現した特定の要素の回数を配列Cのindex順に割り当て…
quick sortは最も高速な探索アルゴリズムの一つ。 最速でO(n)ただ最悪の場合はO(n2)にもなりうる。 partitionと組み合わせて使用する。 partitionは数列のランダムな位置から1ヶ所要素を決める。これをpivotと呼ぶ。pivotを数列の右端に移動し、残りの要素…
8月中旬の院試に向けて勉強してます。 自分の理解度を確認するためのメモ程度に記載してます。他の人が読むと図表も入ってないので、かなり読みにくい内容になってると思います。
ハッシュ法は検索アルゴリズムの一つ。 各データ(keyと呼ぶ)の挿入するべき位置をハッシュ関数を用いて求める。 ハッシュ関数で求めた値、ハッシュ値が配列の挿入するべき位置(インデックス)を示す。 ハッシュ関数 Hash(key)=key mod m ここでmをテーブルサ…