陣地取りのデータ構造（vector編）

前回の続き。

陣地に隣接する空き領域を次々と陣地に加えていく陣地取りアルゴリズムで、次に陣地に加えることの出来る空き領域を管理するデータ構造は何が良いかという話。

行う操作は次の通り。

一覧の中から１つをランダムに『取得』。
選んだマスを一覧から『検索』して『削除』。
（上下左右の）次の候補のマスが一覧にあるか『検索』し、なければ『追加』。

vectorの場合の、それぞれの処理速度は、

『削除』… O(n)
『検索』… O(n)
『追加』… O(1)
『取得』… O(1)

１つのマスを陣地にするのに必要な処理を合計すると………

『取得』＋(『検索』＋『削除』)＋４×（『検索』＋『追加』）

O(1) + (O(n) + O(n)) + 4*(O(n) + O(1)) = 6*O(n) + 5*O(1)

となります。

---

昔こんな↑書き方をしたら
「ばかも～～ん。O(n)ってのは関数の集合で、集合には加算も乗算も定義されとらんわいっ！」
と怒られました。

正しく書くなら、

『削除』の処理時間をf_del(x)、『検索』f_search(x)、『追加』f_add(x)、『取得』f_ref(x)とすると、
f_total(n) = f_ref(n) + (f_search(n) + f_del(n)) + 4*(f_search(n) + f_add(n))
ただし f_del(n)∈O(n)、f_search(n)∈O(n)、f_add(n)∈O(1)、f_ref(n)∈O(1)

だそうです。
でも、面倒なので6*O(n) + 5*O(1)の様な書き方をします。

---

閑話休題。

vectorに対する削除処理はO(n)ですが、今回の様な場合には、データの順番に意味がないので、削除処理を次の様に実装してしまえばO(1)で実行可能です。

template<typename T>
void del_vector(std::vector<T>& data, int n)
{
    data[n] = data[data.size() - 1];
    data.resize(data.size() - 1);
}

また、削除対象を見つける検索処理は不要です。

そんなわけで、vectorを使った場合、陣地を1つ増やすのに必要な処理時間はO(n)になります。

『取得』＋『削除』＋４×（『検索』＋『追加』）
= O(1) + O(1) + 4*(O(n)+O(1)) = 4*O(n) + 6*O(1)
= O(n)

今日の一冊
	数の悪魔―算数・数学が楽しくなる12夜 作者: ハンス・マグヌス エンツェンスベルガー 出版社/メーカー: 晶文社 発売日: 1998/08 メディア: 単行本

タグ：C++