探索アルゴリズム (2)

前回に引き続き、今回もリスト探索のアルゴリズム 2分探索 を紹介します。
このアルゴリズムではリスト内から探索対象を探すのに O(log n) の計算量しかかかりません。

ただし、前提条件として、リストがランダムアクセス可能で、かつソート済である必要があります。

アルゴリズムの内容は至って単純で、探索対象とリストの探索範囲の中央にある要素を比較します。このとき (さらに…)

2010年4月21日 | カテゴリー：アルゴリズム

探索アルゴリズム (1)

そろそろソートアルゴリズムもネタが尽きてきましたので、探索アルゴリズムを紹介します。
まずはリスト探索アルゴリズムの線形探索を紹介します。

リストからオブジェクトを見つけるときにまず思いつくのは、リストの最初の要素から順番に調べていく、というものはないでしょうか。線形探索とはこのアルゴリズムのことです。

探索には n をリストの長さとして O(n) の計算時間量になります。

(さらに…)

2010年4月6日 | カテゴリー：アルゴリズム

ソートアルゴリズム (14)

しつこくソートアルゴリズムを紹介します。今回はスムースソート (Smooth Sort) です。

このソートは以前に紹介したヒープソートを改良したものです。最悪計算時間はヒープソートと同様に O(nlogn) ですが、ソート対象が既に順番に並んでいるほど計算時間は少なくなり、完全にソート済みの場合の計算時間は O(n) となります。

(さらに…)

2010年3月24日 | カテゴリー：アルゴリズム