「フィボナッチヒープ」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: '【ふぃぼなっちひーぷ (Fibonacci heap)】 $F$ ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒー...')
 
1行目: 1行目:
 
【ふぃぼなっちひーぷ (Fibonacci heap)】
 
【ふぃぼなっちひーぷ (Fibonacci heap)】
  
−
$F$ ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O$(n)$ となりうるが, $n$ 回の挿入, $m$ 回の最小値の取り出し, $k$ 回の値の減少を行う合計の計算時間が O$(n+m+k\log n)$ となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの $n$ に対しては計算時間が大きく, 実際には通常のヒープが多く使われている.
+
<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> に対しては計算時間が大きく, 実際には通常のヒープが多く使われている.

2007年7月13日 (金) 13:37時点における版

【ふぃぼなっちひーぷ (Fibonacci heap)】

ヒープとも呼ばれる. 最小値をもつ要素の取り出しと, 要素の値の減少を高速化したヒープ. 1回の操作は最悪で O となりうるが, 回の挿入, 回の最小値の取り出し, 回の値の減少を行う合計の計算時間が O となる. 最短路問題のアルゴリズムの1つはこのヒープを使用している. 複雑な操作を行うので, 実用的な大きさの に対しては計算時間が大きく, 実際には通常のヒープが多く使われている.

「https://orsj-ml.org/orwiki/wiki/index.php?title=フィボナッチヒープ&oldid=4253」から取得