「動的木」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【どうてきぎ (dynamic tree)】 | + | '''【どうてきぎ (dynamic tree)】''' |
最も多くの機能をもつ二分木形状のデータ構造. 大きさ <math>n\,</math> の木構造のグラフを二分木により保持し, 頂点の追加・削除, 木の分割・合併, ある頂点を根にする, ある値をもつ頂点があるか確認, 与えられたパス上の頂点の重みの最大値・総和を計算, ある頂点の子孫の重みの最大値・総和を計算, といった操作をすべて O<math>(\log n)\,</math> 時間で行う. 動的木は非常に複雑であるので, 構造が単純で, <math>m\,</math> 回の操作の合計計算時間が O<math>(m\log n)\,</math> となるスプレー木が多く使われる. | 最も多くの機能をもつ二分木形状のデータ構造. 大きさ <math>n\,</math> の木構造のグラフを二分木により保持し, 頂点の追加・削除, 木の分割・合併, ある頂点を根にする, ある値をもつ頂点があるか確認, 与えられたパス上の頂点の重みの最大値・総和を計算, ある頂点の子孫の重みの最大値・総和を計算, といった操作をすべて O<math>(\log n)\,</math> 時間で行う. 動的木は非常に複雑であるので, 構造が単純で, <math>m\,</math> 回の操作の合計計算時間が O<math>(m\log n)\,</math> となるスプレー木が多く使われる. | ||
| + | |||
| + | [[Category:組合せ最適化|どうてきぎ]] | ||
2008年11月13日 (木) 12:52時点における最新版
【どうてきぎ (dynamic tree)】
最も多くの機能をもつ二分木形状のデータ構造. 大きさ の木構造のグラフを二分木により保持し, 頂点の追加・削除, 木の分割・合併, ある頂点を根にする, ある値をもつ頂点があるか確認, 与えられたパス上の頂点の重みの最大値・総和を計算, ある頂点の子孫の重みの最大値・総和を計算, といった操作をすべて O 時間で行う. 動的木は非常に複雑であるので, 構造が単純で, 回の操作の合計計算時間が O となるスプレー木が多く使われる.
