[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
競技プログラミングにハマるプログラマのスレ 227 http://medaka.5ch.net/test/read.cgi/prog/1747628087/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
255: 仕様書無しさん [sage] 2025/05/22(木) 02:07:16.24 Skew Heap の償却 O(log n) が成り立つ理由 1. すべての操作は meld（ヒープの結合）に帰着する ・insert : 1 要素ヒープと既存ヒープを meld ・delete-min : 根を削除 → 残った左右の子のヒープを meld meld の手順 (a) 2つのヒープの根を比較し、キーが小さい方の根を新しいヒープの根とする。 (b) (a)で選ばれた根の元の右の子と、もう一方のヒープ全体を再帰的に meld する。 この結果が、(a)で選ばれた根の新しい右の子となる。 (c) (a)で選ばれた根の左右の子を swap する。 ← skew heap の特徴（再帰から戻る度に行う） 2. 実際のコストは「再帰で降りたノード数（meldパスの長さ）」 最悪ケースでは、右に偏った鎖状のヒープだとパスが長くなり O(n) になることがある。 3. なぜ償却 O(log n) になるのか（概念的な説明） ・meld 操作はヒープの右パスに沿って行われ、各ノードで左右の子をスワップする。 ・もし右パスが非常に長い場合、その操作の実際のコストは高くなる。 ・しかし、多くのスワップが行われることで、これまで右側に集中していた部分木が左側に移り、 ヒープの右側への偏りが是正される傾向がある。 ・つまり、コストが高い操作は、その分ヒープの「バランス」を改善する効果がある。 ・この「改善」を会計的に扱うのがポテンシャル解析。 http://medaka.5ch.net/test/read.cgi/prog/1747628087/255
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 747 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.007s