探索アルゴリズム (1)

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

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

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

(さらに…)

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

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

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

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

(さらに…)

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

フィボナッチ数

フィボナッチ数という数をご存知でしょうか。今回はフィボナッチ数を求めるアルゴリズムについて考察してみます。
まずフィボナッチ数とは次のように定義される数のことです。

n番目のフィボナッチ数を F(n) として

1.F(0) = 0
2.F(1) = 1
3.F(n) = F(n – 1) + F(n – 2) (さらに…)

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