[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

261: 05/22(木)02:22 AA×


[240|320|480|600|100%|JPG|べ|ﾚｽ栞|ﾚｽ消]
261: [sage] 2025/05/22(木) 02:22:11.19 償却コスト A は、 A = C + ΔΦ = O(m) + m_LH - m_RH です。 m = m_RH + m_LH + m_EQ （ここで m_EQ は size(L_i) <= size(R_i) であり、スワップ後もRightHeavyにならないノード）とすると、 A = O(m_RH + m_LH + m_EQ) + m_LH - m_RH A ≈ O(1) * (m_RH + m_LH + m_EQ) + m_LH - m_RH = O(m_LH + m_EQ) + (const-1)m_RH もし実際のコストの係数が1に近いと仮定できれば、A ≈ 2m_LH + m_EQ となります。 ここで重要なのは、m_LH + m_EQ の部分、つまりmeldパス上で元々 size(R_i) <= size(L_i) であったノードの数です。 あるノード x で size(rc(x)) <= size(lc(x)) が成り立つ場合、size(rc(x)) <= (size(x) - 1) / 2 となります。これは、右の子の部分木のサイズが、その親を根とする部分木全体のサイズの半分以下であることを意味します（左の子が存在する場合）。 このような性質を持つノードが右パスに連続して多数現れると、部分木のサイズは急速に減少します。したがって、任意の右パスにおいて、size(rc(x)) <= size(lc(x)) を満たすノードの数は高々 O(log n) 個しか存在できません。 Meld操作がたどる右パス上のノードのうち、m_LH と m_EQ に分類されるノードは、まさにこの条件 size(R_i) <= size(L_i) を（スワップ前に）満たしています。 よって、m_LH + m_EQ = O(log n) となります。 したがって、償却コスト A = O(m_LH + m_EQ) = O(log n) と結論付けられます。 http://medaka.5ch.net/test/read.cgi/prog/1747628087/261
償却コスト は です ここで は でありスワップ後もにならないノードとすると もし実際のコストの係数がに近いと仮定できれば となります ここで重要なのは の部分つまりパス上で元 であったノードの数です あるノード で が成り立つ場合 となりますこれは右の子の部分木のサイズがその親を根とする部分木全体のサイズの半分以下であることを意味します左の子が存在する場合 このような性質を持つノードが右パスに連続して多数現れると部分木のサイズは急速に減少しますしたがって任意の右パスにおいて を満たすノードの数は高 個しか存在できません 操作がたどる右パス上のノードのうち と に分類されるノードはまさにこの条件 をスワップ前に満たしています よって となります したがって償却コスト と結論付けられます

---

上下前次1-新書関写板覧索設栞歴

---

あと 741 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.034s