[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
競技プログラミングにハマるプログラマのスレ 227 http://medaka.5ch.net/test/read.cgi/prog/1747628087/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
262: 仕様書無しさん [sage] 2025/05/22(木) 02:22:26.88 3. 参考資料 この種の償却解析の議論や技法は、以下の資料やそれらに類するデータ構造の教科書、講義ノートで見られます。 1) Sleator, D. D., & Tarjan, R. E. (1985). Self-Adjusting Binary Search Trees. Journal of the ACM, 32(3), 652-686. - 直接Skew Heapを主題としたものではありませんが、Splay Treeの償却解析の技法が広く応用されており、AppendixでSkew Heapに似た「ボトムアップヒープ」について触れています。ポテンシャル関数を用いた償却解析の基礎となります。 2) Weis
s, M. A. (various editions). Data Structures and Algorithm Analysis in C++ / Java. Addison-Wesley. - 多くの版でSkew Heapとその償却解析について解説が含まれています。 3) 大学の講義資料: - "Skew Heap amortized analysis" や "Skew Heap potential function" といったキーワードで検索すると、多くの大学（例：MITのErik Demaine教授の高度なデータ構造の講義など）の講義ノートやスライドが見つかり、そこで同様のポテンシャル関数を用いた解析が紹介されています。具体的なポテンシャルの定義は若干異なることがあ
りますが、基本的なアイデアは共通しています。 この解析は、Skew Heapの単純なスワップ操作が、長期的にはヒープのバランスを効率的に保つことを示しています。 http://medaka.5ch.net/test/read.cgi/prog/1747628087/262
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 740 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.007s