[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上
下
前
次
1-
新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
262
: 05/22(木)02:22
AA×
[
240
|
320
|
480
|600|
原寸
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
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) Weiss, 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
参考資料 この種の償却解析の議論や技法は以下の資料やそれらに類するデータ構造の教科書講義ノートで見られます 直接 を主題としたものではありませんが の償却解析の技法が広く応用されておりで に似たボトムアップヒープについて触れていますポテンシャル関数を用いた償却解析の基礎となります 多くの版で とその償却解析について解説が含まれています 大学の講義資料 や といったキーワードで検索すると多くの大学例の 教授の高度なデータ構造の講義などの講義ノートやスライドが見つかりそこで同様のポテンシャル関数を用いた解析が紹介されています具体的なポテンシャルの定義は若干異なることがありますが基本的なアイデアは共通しています この解析は の単純なスワップ操作が長期的にはヒープのバランスを効率的に保つことを示しています
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 740 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
ぬこの手
ぬこTOP
0.035s