「フィボナッチヒープ」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【ふぃぼなっちひーぷ (Fibonacci heap)】 | + | '''【ふぃぼなっちひーぷ (Fibonacci heap)】''' |
<math>F\,</math> ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O<math>(n)\,</math> となりうるが, <math>n\,</math> 回の挿入, <math>m\,</math> 回の最小値の取り出し, <math>k\,</math> 回の値の減少を行う合計の計算時間が O<math>(n+m+k\log n)\,</math> となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの <math>n\,</math> に対しては計算時間が大きく, 実際には通常のヒープが多く使われている. | <math>F\,</math> ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O<math>(n)\,</math> となりうるが, <math>n\,</math> 回の挿入, <math>m\,</math> 回の最小値の取り出し, <math>k\,</math> 回の値の減少を行う合計の計算時間が O<math>(n+m+k\log n)\,</math> となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの <math>n\,</math> に対しては計算時間が大きく, 実際には通常のヒープが多く使われている. | ||
| + | |||
| + | [[Category:組合せ最適化|ふぃぼなっちひーぷ]] | ||
2008年11月13日 (木) 15:31時点における最新版
【ふぃぼなっちひーぷ (Fibonacci heap)】
ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O となりうるが, 回の挿入, 回の最小値の取り出し, 回の値の減少を行う合計の計算時間が O となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの に対しては計算時間が大きく, 実際には通常のヒープが多く使われている.
