アルゴリズムとデータ構造
https://gyazo.com/49f7b2337e386cd0b12d4f1327439fcb
いくらコンパイラーがはやくても小手先でしかないアルゴリズムの方が重要
アルゴリズムと計算量
配列の先頭から順番に確認していく方法
計算量O(1)
値の挿入はただ末尾に追加すればいいだけだから高速
半分の箇所から既定値を確認してその値が大きいか小さいかを確認して絞り込んでいくアルゴリズム
つまりあらかじめ配列のデータがソートされていないとこのアルゴリズムは使えない
計算量O(n)
値の挿入は元の構造を維持しないといけないのでちょっと大変
最大時間計算量と平均時間計算量を意識する必要がある
領域計算量も大事
データ構造
ランダムな参照と挿入、削除の両方を高速に行うことは現実的に不可能
配列
任意の要素を高速に参照できる
挿入と削除が遅い
リスト
挿入と削除ははやい
順序を制限しない限り要素の参照は遅い
探索
計算の途中結果を残しておき記録してから別の計算をはじめてのちほど 計算を再開するような場合に最適
一方の端から挿入してもう一方の端から取り出す
待ち行列
デキュー
スタックとキューの兼ね合わせ
木（tree）
走査を親からしていくか子からしていくのいずれかがある
探索
探索は探す作業と作る作業の速さを同時に意識しないといけない
1つ1つ順に端から調べる
計算量はループを回す回数に比例していく
はやく見つけることができれば計算量ははやい
最後に見つかるともっとも計算量が多い
表を作る祭に、重複を無視できれば計算量は0(1)
しかし重複チェックとなると探索と同じでO(n)になる
n+1番目に予め目標となるキーの値を入れておくと求めるレコードが存在しない場合でもn+1番目に来ればキーの値のの等しいデータにぶつかる
キーを与えて大小を比較する
与えられたキーが比較対象のキーより小さいときは大きい方の比較はしなくてよい
二分探索とはことなる技法
木を作る時に親からみて小さい方が左に大きい方が右に分かれるように整列された木のこと
どのノードの左右部分木の高さの差も1以下
左回転、右回転してノードを動かす
バランスが取れている木であれば計算量が0(log n)になる
子供の最大数がm個ある木
最小数はm/2
depthは一緒
つまりもっともバランスの取れた構造になっている
二分探索木と同じで上から調べていく
どの子供を選んで下がるかは左右の葉の間にキーがありそれで調べる
左が小さく右が大きい
チェイン法
線形走査法
二重ハッシュ法
ハッシュ表の容量に余裕がある場合は使える
けど一定の割合を超えてしまうと使うのは難しい
整列
問題をいくつかの部分に分割してそれぞれを解きその結果を組み合わせて全体の解をえるという方式を分割統治法という クイックソートと同様にオーダーとしてとは最善の性能をもつ
グラフのアルゴリズム
辺に矢印があるものとないものがある
無向グラフ
有向グラフ
行列を使ってグラフを表現する
訪問済みの箇所を記録して辿らないようにする