WEB+DB(vol91)で使えそうな連載記事がありますのでブログにメモリます。
テーマはデータ構造です。
Contents
データ構造とは?
主にハッシュと配列。
- 配列:データを順番に入れる
- ハッシュ:ラベルにより検索できるがデータの順番は通常保持されない
計算量
コンピューターが行わなければいけない計算の量
プログラムとメモリ
通常プログラムではデータをメモリ(データを置く場所)におく。
ポインタはメモリの番地を指し示すもの(参照なのでデータ自体は入っていない)が入っている。
配列について
配列の宣言
- 要素分のアドレスが連続した領域に確保される
- その領域の先頭のアドレスが変数に保存される
メリット
要素が連続して並んでいることと、変数のサイズがわかっていれば、アドレスがわかればその場所をすぐに特定できるため、計算量が少ない
デメリット
逆に要素数の増減に弱い。要素数５→6にしようと思ったときにすぐに増やせない(５番目のメモリの隣がすでに使われていることがあるため、確保できない。)６個分の値がコピーできる領域を探して、一度コピーする必要がある
配列の欠点を補うべくして連結リストが生まれた。
連結リストについて
配列と同じデータ群だが、４つのアドレスが連続している必要はなく、自分自身の値と、次の値の参照だけをもつ
メリット
次の値の参照を持っているので、値の増減が楽。
デメリット
任意のアドレスに飛ぶ場合、各アドレスがばらばらに配置されているため、リストの要素に応じた時間がかかってしまう(100個あった場合、98番目を探したりするのが大変)
ここらへんはWEB+DBの図を見るのがわかりやすいかも.
オーダー記法
アルゴリズムの計算量を測る方法
- O(1) データ量が増えても変わらない
- O(logn) データが増えても計算量はゆっくりとしか増えない。数学のlog
- O(n) データ量に正比例して増える
- O(n^2) データ量の２乗になる
JavaでいうとArrayListは配列の要素があるのでアクセスに強い
中央部のデータの増減に関してはO(n)になる一方、検索に対してはO(1)
逆にLinkedListは参照なのでデータの増減に対してはO(1)になる一方、検索はO(n)になる。
下記のリンクがわかりやすい
