[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
11: 05/19(月)17:16:03.40 AAS
>>4
blackyuki
146: 05/20(火)20:22:00.40 AAS
mayobun
256: 05/22(木)02:07:22.40 AAS
4. ポテンシャル解析の考え方
・ヒープの「アンバランスさ」や「右への偏り具合」を数値化したものを「ポテンシャル」と考える。
・実際のコストが高い操作（長い右パスをたどる）では、多くのスワップにより
「アンバランスさ」が大きく解消され、ポテンシャルが大幅に減少する。
・償却コスト = 実際のコスト + ポテンシャルの変化量
・実際のコストが高くても、ポテンシャルの減少が大きければ、償却コストは小さく抑えられる。
・逆に、実際のコストが低い操作ではポテンシャルが少し増えることもあるが、
それは将来のコストが高い操作のための「貯金」のようなもの。
・ポテンシャル関数をうまく定義し数学的に解析すると、どの操作も平均して
O(log n) の償却コストになることが示せる。
省5
547: 05/23(金)17:47:56.40 AAS
鹿児島って住みづらそうだな
825(1): 05/25(日)12:42:11.40 AAS
りにりすさんは多言語を扱うわかりやすい天才だから疑義はないですね
877: 05/25(日)19:26:10.40 AAS
利用規約なんて読んで理解したとしても無視するに決まってんだろ
なぜなら私達は競プロerだからです
954: 05/25(日)20:24:41.40 AAS
バカ参り定期
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.039s