Webエンジニアのブログ

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の基本編をまとめてみる

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造という本で最近アルゴリズムの勉強をやってた。アルゴリズムを体系的に知っておくだけでも今後に役立つかなー、というノリで買ったんだけど、結構分かりやすくて楽しめて学ぶことができた。

とりあえず基本編が終わったので、アルゴリズムをここに一通りまとめてみる。

AIZUのステータスページは一応ここ。 AIZU ONLINE JUDGE

初等的整列

ソートとは、データをそれらが持つキーを基準に昇順または降順に並び替える処理のこと。 キーの値が同じ要素を2つ以上含むデータをソートした場合、処理の前後でそれらの順番が変わらないようなアルゴリズムを安定なソートと呼ぶ。

挿入ソート

挿入ソートは、整列してある配列に追加要素を適切な場所に挿入する安定なソート。計算量はO(n^2)。 整列されている部分が多いほど計算量が減るが、降順を昇順にする場合などはもっとも遅くなる。

バブルソート

バブルソートは、隣り合う要素の大小を比較しながら整列させる安定なソート。計算量はO(n^2)。 またバブルソートの交換回数は、反点数または転倒数と呼ばれるもので、列の乱れ具合を表す数値としても知られている。

選択ソート

選択ソートは、未ソート部分の配列から最小値または最大値を見つけ出し、ソート済み部分の配列の次と入れ替える不安定なソート。計算量はO(n^2)。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うための、一定の形式に系統立てて格納するときの形式のこと。

スタック

スタックは、データを後入れ先出しの構造で保持するもの。 逆ポーランド記法で記述された数式は、スタックを用いて計算を行うことができる。メモリ管理などの低レイヤーでも使われているアルゴリズム。

キュー

キューは、データを先入れ先出しのリスト構造で保持するもの。 配列でキューを実装する際、最初のキューを取り出すときにデータ全体を前に向かって移動するような処理をしていては、その度にO(N)の計算が必要になってしまう。そのため配列をリングバッファとみなし、ポインタを循環させるようにして移動が必要ない管理方法を取る。

連結リスト

双方向連結リストは、各データが前の要素と次の要素へのポインタを持っている。

リストへの要素の追加は、いくつかのポインタを繋ぎ変えるだけなのでO(1)で行うことができる。 配列ではA[1]のように定数時間で指定した要素にアクセスできるが、リストでは要素を特定するためにポインタをたどる必要があるため、N個の要素を含むリストに対する検索はO(N)のアルゴリズムになる。

また要素の削除については、先頭/末尾の削除はO(1)で行うことができるが、特定の要素の削除は特定が必要であるためO(N)の計算量が必要になる。 このデータ構造自体はあまり実用性はないが、後に扱うデータ構造の部品として活かすことができる。

探索

探索あるいは検索とは、データの集合の中から目的の要素を探し出す処理のこと。

線形探索

線形探索は、配列の先頭から各要素が目的の値と等しいかどうかを順番に調べる検索アルゴリズム。計算量はO(n)。

二分探索

二分探索は、ソート済みの配列の中央の値を見て、検索したい値が中央の左にあるか右にかるかを判断し、片方には存在しないことを確かめながら検索していく検索アルゴリズム。計算量はO(log2n)。

ハッシュ法

ハッシュ法は、各要素の値に応じて格納場所を管理するハッシュテーブルを用いた検索アルゴリズム。

再帰・分割統治法

分割統治法は、大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決するという問題解決の手法のこと。 再帰関数とは、関数の中で自分自身を呼び出すような関数を指す。

全探索

全探索、またはしらみつぶし探索は、単純だが汎用的な問題解決方法であり、全ての可能性のあるもの体系的に数え上げていく方法のこと。

高等的整列

マージソート

マージソートは、既に整列してある複数列を1個の列にマージする際、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップ式の分割統治法を使ったソートアルゴリズムのこと。計算量はO(n log n)。

パーティション

パーティションは、ある基準に基づいて列を複数に分割する手法のこと。

クイックソート

クイックソートは、パーティションを再帰的に繰り返して列を整列するソートアルゴリズムのこと。計算量はO(n log n)。 マージソートのように別の配列を生成しないインプレースソートであるため、余計なメモリを消費しない。

計数ソート

計数ソート、またはバケットソートは、整列したいデータの値がm種類であるとき、m個のバケツを用意して値ごとにバケツを対応付けてソートするアルゴリズムのこと。計算量はO(n + m)。

木構造

木構造とは、階層的な構造を表すのに適したデータ構造のこと。

根付き木

木の高さをhとして各節点の深さを求める計算量はO(h)となり、全ての節点の深さを求めるとO(nh)となる。

二分木

二分木とは、1つの根を持ち、全ての節点の子の数が2以下である木構造のこと。

木の巡回

二分木の巡回は、各節点へ1度ずつ訪問するので、O(n)の計算量となる。

二分探索木

二分探索木は、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木のこと。

挿入の計算量は、木の高さをhとするO(h)となる。節点の個数をnとすると、入力に偏りがなければO(logn)となる。探索の探索量も、挿入と同じくO(h)である。 削除の計算量は、ノードの探索のためにO(h)、そして次節点を求めるためにO(h)を必要とするため、O(h)となる。

このように二分探索木は挿入などの計算量がO(logn)となるように実装されている。これらの計算量になるためには常に木の高さをできるだけ低く維持する必要がある。このようなバランスをとれた木を平衡二分探索木と呼ぶ。

ヒープ

ヒープは、優先度付きキューを実装するにあたってよく使われるデータ構造のこと。

完全二分木とは、全ての葉が同じ深さを持ち、内部節点の子の数が2である二分木のことを指す。 二分ヒープは、完全二分木を1つの配列に対応させたデータ構造のこと。

グラフ

グラフとは、対象の集合とそれらのつながりの集合を表すデータ構造のこと。 エッジに方向がある有向グラフや、方向が無い無向グラフ、そしてそれぞれに重み付き無向/有向グラフがある。また表現法には隣接行列表現や隣接リスト表現などがある。


{ "name": "hareku", "job": "Web Engineer" }