エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Splay 木の計算量解析 - ブログ名
Splay 木概論 Splay 木の基本操作 $\newcommand {\rank}{\mathtt{rank}}$Splay 木 $T$ は $0 ≤ Φ(T) ≤ n... Splay 木概論 Splay 木の基本操作 $\newcommand {\rank}{\mathtt{rank}}$Splay 木 $T$ は $0 ≤ Φ(T) ≤ n \log(n)$(ただし $n$ は節点数)なるポテンシャル $Φ(T)$ のもと、次の操作ができる二分木です。 クエリ 引数 事前条件 効果 ポテンシャル増分 最悪時間計算量 $\mathtt{splay}$ 節点 $u$ なし inorder を保って $u$ が根になるように変形する $O(\log(n)) - h(u)$ $O(h(u))$ 従って次のことがわかります。 $\mathtt{splay}$ をばかりを $q$ 回連続して呼んだ場合、$O( (n + q)\log(n))$ 時間かかります。(なお実コストのほうで解析すると $O(nq)$ であることもわかり、$q = o(\log(n))$ のとき