[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
261: 05/22(木)02:22 AAS
償却コスト 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) と結論付けられます。
上下前次1-新書関写板覧索設栞歴
あと 741 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.006s