アルゴリズムとデータ構造1

アルゴリズムとデータ構造1
2009年7月6日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2009/index.html
演習の解答の要点
1.
2.
3.
4.
5.
比較対象がリストの要素と等しいかどうかはequals()の実装で決めるべき
だから。オブジェクトの何が等しいか？はプログラマが決めること。
リストを最初から最後までたどって数えないといけないから、O(n)。
配列へのデータ挿入なので、O(n)。
i) clear()
ii) add(0, element) または add(element)
iii) return remove(0) または return remove(size)-1)
i) clear()
ii) add(element)
iii) return remove(0)
E remove(int index)では、削除対象を返す。
というか、削除対象ではないものが返るとしたら、何を返すというのだ？
配列上の探索
添え字を用いて
直接アクセス
先頭から
順に調べる
直接探索
線形探索
public class Array
{
public Array(int aMaxSize)
{
this.array = new String[aMaxSize];
this.number = 0;
}
}
public int search(String aTarget)
{
for(int count = 0; count < this.number; count++){
if(aTarget.equals(this.array[count])){
return count + 1;
}
}
return -1;
}
private String[] array;
配列の要素が尽きたかどうかの判定
private int number;
目的のデータであるかどうかの判定
１つのデータを探すのに2回も判定
番兵
• 計算量は減らないが、実行時間は減る
• アルゴリズムではなくテクニックのひとつ
• 線形探索では番兵を最後尾に置く
– 線形探索における番兵では、探索したいデータと等
しい値のデータを用いることが多い
– 探索は目的のデータか番兵いずれかの発見で終了
– 探索対象が無くなったかどうかの判定が不要になる
• 番兵は最も後に探索され、そして必ず一致する
public class Array
{
public Array(int aMaxSize)
{
this.array = new String[aMaxSize+1];
this.number = 0;
}
}
public int search(String aTarget)
{
int count=0;
これが番兵
this.array[this.number] = aTarget;
while( !aTarget.equals(this.array[count]) ){
count++;
}
if(count != this.number){
return count + 1;
}
配列の要素が尽きたかどうかの判定
return -1;
目的のデータであるかどうかの判定
}
private String[] array;
配列の要素が尽きたかどうかの判定
private int number;
を最後に1回だけにした
二分探索
ノード数をNとすると
O(log N)
の計算量で探索できる
29
20
木が偏っているときは
最悪O(N)になるが…
14
7
32
24
19
21
30
48
31
public class BinarySearchTree
{
public BinarySearchTree()
{
this.root = null;
public MyNode search(MyData aData)
}
{
private MyNode root;
if(null == this.root){
}
return null;
}
MyNode currentNode = this.root;
while(true){
if(0 == currentNode.getData().compareTo(aData)){
return currentNode;
}
if(0 < currentNode.getData().compareTo(aData)){
if(null == currentNode.getLeft()){
return null;
}
currentNode = currentNode.getLeft();
}else{
if(null == currentNode.getRight()){
return null;
}
currentNode = currentNode.getRight();
}
}
}
最悪の形（二分探索木）
48
32
31
ノード数をNとすると
O(log N)
の計算量で探索できる
30
29
木が偏っているときは
最悪O(N)になるが…
24
21
20
19
木の深さをバランスよく
したものを平衡木という
14
7
次は平衡木について述べる
B木（B-tree）
二分木ではないが、探索用のｍ分木
いわゆる平衡木
順序木である
B木を構成するためのルール
根から葉までの深さはどの葉についても同じである
各頂点（葉以外）の子の数は最大mである
各頂点（葉以外）の子の数は最小
である
 は切り上げを意味する記号である
根は例外で、最小2である
頂点の構造
頂点にはデータは置かない
探索キーだけをおく
キーは枝をたどるときの境目
B木の探索
途中の頂点にはデータは入ってない
入ってる値は部分枝の選択のためのキー値
データは葉の部分におかれている
そうしない実装もある
根から部分木を選択しながら下降する
部分木の選択にはO(log m)必要
葉に達したら探索は終了
葉の値と一致すれば成功、そうでなければ失敗
B木の頂点に置く境界値
• 頂点に置かれる値は部分木選択に使われる
• 境界値の条件は次の２つを満たす
– 左に位置する部分木の最大値以上
– 右に位置する部分木の最小値以下
• 条件を満たす値は複数あるがどれでもいい
境界値
境界値の左部分木
境界値の右部分木
29を探索
3を探索
44を探索
7
7以上31未満の数
7未満の数
3
0
22
6
3
31
6
7
31以上の数
29
22
49
29
31
-
-
49
探索失敗
•未満, less than, より小さい
•以上, greater than or equal to
•以下, less than or equal to
新しいデータ（子）を追加するとき
1. 追加すべき位置（親の頂点）を決定します
2. 親の頂点に空きがあるか調べます
3. 空きがない場合は親の頂点を分割します
親の親の頂点から新たに枝を増やします
親が根である場合は、新たな根を親の親として増やします
4. 子を頂点に追加します
データ（子）を削除するとき
1. 削除すべきデータを探索し、削除します
2. 親からの枝の本数が最少数を満たすかどうか調べます
3. 最少数に満たない場合は隣の頂点と子を按分します
按分した結果最少数を満たせない場合は隣の頂点と併合します
親が根である場合に最少数２を割ったら、根を削除します
計算量の考察
• キー値の比較を1回行うと候補は半減する
– 候補が半減する場合がもっとも効率が良い
– 半減するようにデータを保持する
• 例：平衡木を使う
• ちょうど半分ずつ絞りこめばO(log N)
• キーの比較という手法を使う限りはこれ以
上探索の効率はよくならない。

Download Report