|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
フィボナッチヒープ（Fibonacci heap）とは、計算機科学におけるデータ構造（ヒープ）の1つ。 フィボナッチヒープの名前は、処理時間を解析する際にフィボナッチ数が使用されたことによる。 ==概要== フィボナッチヒープは1984年にMichael L. Fredmanとロバート・タージャンの二人によって開発され、1987年に科学雑誌に最初に掲載された。フィボナッチヒープを導入することで、ダイクストラやPrimのアルゴリズムを含めたいくつかのグラフアルゴリズムの実行時間を改善したことで最もよく知られている。 二項ヒープとよく似たデータ構造であるが、より償却実行時間が短くなる。フィボナッチヒープはグラフ内で最短経路を計算するためのダイクストラ法や、グラフの最小全域木を計算するプリム法のおおよその処理時間を改善するのに用いられる。 特に、挿入、最小値検索、キー値減算、マージの操作は一定償却時間内で完了する。削除と最小値削除の操作はO(log n)時間内で完了する。つまり、空のデータ構造から始めて最初のグループから「a」個の操作を行い、次に二番目のグループに「b」個の操作を行う任意のシーケンスでは、O(a + b log a)の時間で完了する。 二項ヒープでは、このような一連の操作ではO((a + b)log(n))時間かかる。aよりbがおおよそ小さい場合はフィボナッチヒープは二項ヒープよりよくなる。 空の構造から一連の操作にかかる時間は上で述べた範囲内に収まるが、いくつかの(非常にまれな)操作では非常に長い時間かかることがある(特にキー値減算、要素の削除、最小値の削除にかかる時間は、最悪の場合要素数に比例する)。この理由により、フィボナッチヒープ及びそれを用いているデータ構造はリアルタイムシステムにはふさわしくないかもしれない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「フィボナッチヒープ」の詳細全文を読む スポンサード リンク
|