アルゴリズムとデータ構造関連で知ったことをまとめる part 1
目次
概要
アルゴリズムに関する基本的な用語
全探索
全探索とは、考えられるすべての可能性を調べ上げることです
線形探索
線形探索とは、一つ一つのデータを順に調べていくことです。
アルゴリズム
アルゴリズムとは、解が定まっている「計算可能」な問題に対して、解を正しく求めるための手続きのことです。 ja.wikipedia.org
設計技法
設計技法とは、アルゴリズムを設計するのに役にたつ考え方のことです。設計技法の一つに貪欲法や動的計画法などがあります。
貪欲法
貪欲法とは、ある問題を部分問題に分割して、その部分問題の最適解をそれぞれ独立に求めて、評価値の高い順に取り込んでいくことで、問題の解を出す考え方のこと
余談ですが、部分問題を解く際には、再帰的な考え方をするとうまく行きやすいです。
貪欲法では、必ずしも最適解を求められるわけではないです。ただし、解に近い値を得ることができます。その点を注意しましょう。
区間スケジューリング問題
区間スケジューリング問題とは、それぞれの区間が重複せず、それぞれの区間の数を最大化するためにはどうすればよいかを考える問題である。
この記事がわかりやすかったです。
二分探索
二分探索とは、ソート済みの解の候補を半分にしながら、解を探索していくアルゴリズムです。二分探索はバイナリサーチとも呼びます。
二分探索を使いたいときに重要なのは「質問」です．次のような質問を見つけることが出来たら，二分探索が使えます．
- Yes / No で答えられる質問である．
- あるところを境界として，そこより小さいところではずっと Yes だし，そこより大きいところではずっと No である．
- または，あるところを境界として，そこより小さいところではずっと No だし，そこより大きいところではずっと Yes である．
データ構造に関する基本的な用語
データ構造とは
データ構造とは、効率的に管理されたデータの集合体です。
データ構造に対しての操作をクエリ(データの取得、データの更新、データのインサート等々)と呼びますが、どんなクエリが要求されても、迅速にデータを返せるようにデータ構造を設計する必要があります。
グラフ
グラフとは、対象物の関係性を表すものである。 対象物は頂点と呼び、対象物の関係性を表す線を「辺」と呼びます。 友人関係、鉄道路線、タスクの依存関係など、さまざまな関係性をグラフで表現できます。
有向グラフ、無向グラフ
グラフの各辺には向きが考慮されている時があり、その時のグラフを有向グラフと呼びます。グラフの各辺に向きが考慮されていない時は、無向グラフと呼びます。
サイクル
元のグラフの一部であるグラフのことを、部分グラフと呼びます。 サイクルとは、隣接する頂点を辿っていくことで、元の頂点に戻って来れるような部分グラフのことです。ただし多くの場合、パスは「同じ頂点を二度以上通ってはいけない」ものとします。
木
木とは、連結であり(頂点間に辺が存在する)、かつサイクルを持たない無向グラフのことです。
根付き木
根とは、木において、特別扱いする1つの頂点のことです。 根をもつ木のことを、根付き木と呼びます。根をもたない木に対して、そのことを強調するときは根なし木とよびます。 根付き木を描画するときは、下図のように、根を最も上に描くことが一般的となっています。
葉
葉とは、根を除く頂点のうち、その頂点に接続している辺が 1 本しかない頂点のことです。
親、子
根以外の頂点 v について、v に隣接している頂点のうち、根側にある頂点 p を v の親とよびます。 このとき v は p の子であるといいます。
二分木
二分木とは、すべての頂点に対して子の個数が 2 以下であるような根付き木のことです。
ヒープ
ヒープとは、すべての頂点に対して(親の値) >= (子の値)が成立しているような根付き木のことです。
部分木
根付き木の根以外の各頂点 v の親子関係のことを、部分木と呼びます。
木のデータ構造から値を探索したいなら、再帰処理を使えば良い
部分問題などもそうですが、再帰処理を使うとうまく行きます。
木の高さ
木の高さとは、根付き木の各頂点の深さの最大値のことです。
フィボナッチ数
フィボナッチ数とは、フィボナッチ数列を構成する数のことです。一般にFnと表記されます。
メモ化
メモ化とは、一度計算した再帰関数の結果を配列などに保存しておき、再度同じ関数の計算が必要になった際はそこから参照するテクニックのことです。
これにより、同じ関数の計算結果を何度も再帰呼び出しを用いて計算してしまうことを避けることができます。
