読者です 読者をやめる 読者になる 読者になる

野次馬エンジニア道

野次馬な気持ちでプログラミングをあれこれと綴ります

データ構造 - 計算量・グラフの走査

言語によってはCollectionのクラスが用意されてるのでここでは概念的な部分を軽く見てみる。

計算量

データ構造やアルゴリズムを評価する際に必要な基準。

  • 時間計算量(time complexity)
  • 空間計算量(space complexity)

これらはトレードオフの関係。現実の制約に沿って両方から評価することが重要。

配列・連結リスト

計算量を表すには一般的にO記法がよく用いられる。理解しやすいので配列・連結リストから。

操作 配列 動的配列 連結リスト
検索 O(N) O(N) O(N)
先頭へのアクセス O(1) O(1) O(1)
中間へのアクセス O(1) O(1) O(N)
末尾へのアクセス O(1) O(1) O(1)
先頭への追加・削除 N/A O(N) O(1)
末尾への追加・削除 N/A O(1) O(1)

配列はメモリ上連続した領域なのでインデックスでアクセスできる場合はO(1)。検索は値でみるのでO(N)。

連結リストは次の要素への参照(ポインタ)を持つ構造のため順次走査する必要。 連結リストで挿入位置が分かっている場合はO(1)。不明な場合は、走査がはいるのでO(N)。

動的配列の追加の計算量はならしでO(1)。理由は動的配列への追加コストはなぜ O(1)?のページが分かりやすい。

木・グラフ

続いて木・グラフ。二分木(binary tree)が二分探索木となるためは、左のノードは親よりも小さいか等しく右のノードよりも小さい、という制約がある。

計算量を考える上ではバランスが取れているか(平衡状態にあるか)どうかも重要。平衡でない場合は、平均計算時間・最悪計算時間の両方の観点からアルゴリズムを考える必要がある。

操作 平衡木 非平衡
検索 O(logN) O(N)
追加 O(logN) O(N)

平均O(logN)、ワーストO(N)とでもイメージしておけばいいのだろうか。

グラフの走査

木を見たところでついでに走査を見てみる。深さ優先(Depth First)と幅優先(Breadth First)。深さ優先だとデータの種類によっては余計な走査が増えて不利な場合もある。Javaで実際に書いてみる。

深さ優先探索(DFS)

void searchDFS( Node root ) {
    if( root == null ) return;
    visit(root);
    root.visited = true;
    Node n = null;
    while( (n = root.getAdjacent()) != null ) {
        if( n.visted == false ) {
            searchDFS(n);
        }
    }
}

幅優先探索(BFS)

ポイントはQueue(FIFO)を使うところ。先に同じレベルの位置にあるノードを走査したいから、子のノードのレベルに降りる際にループに入れるようにQueueで覚えておく。

void searchBFS( Node root ) {
    Queue<Node> queue = new LinkedList<Node>();
    visit(root);
    root.visited = true;
    queue.offer(root);
    while(!queue.isEmpty()) {
        Node r = queue.poll();
        Node n = null;
        while( ( n = r.getAdjacent()) != null ) {
            if( n.visited == false ) {
                visit(n);
                n.visited = true;
                queue.offer(n);
            }
        }
    }
}

走査順

下記に分類される。DFSの再帰のコードでイメージするとわかりやすい。

  • pre-order(行きがけ順)
  • in-order(通りがけ順)
  • post-order(帰りがけ順)
void preOrder( Node root ) {
  visit(root);
  preOrder(root.left);
  preOrder(root.right);
}

void inOrder( Node root ) {
  inOrder(root.left);
  visit(root);
  inOrder(root.right);
}

void postOrder( Node root ) {
  postOrder(root.left);
  postOrder(root.right);
  visit(root);
}