作者kronze7109 (Kronze)
看板Grad-ProbAsk
标题［理工］105台大演算法
时间Tue Apr 27 23:42:05 2021
强者大大，大家好
小弟第一次发文
排版混乱麻烦大家多担待
想请问
1.Potential Function的定义
背後的用意想了好久还是无法理解
2. c <= k*logn
是因为前面定义insert . extract-min的worst case为O(n)吗
http://i.imgur.com/Lm8Q4WX.jpg
http://i.imgur.com/wbIbIZT.jpg
先叩谢各位大大了
-----
Sent from JPTT on my Google Pixel 4.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.77.46.4 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1619538127.A.A6B.html
1F：推 kaneson: 位能法当於对毎个操作设计如何改变某个全域变数的量，可 04/28 12:25
2F：→ kaneson: 以有加有减，然後检查连续n个任意操作过程中这个值都不会 04/28 12:25
3F：→ kaneson: 比起始低，就是个ok的设计。此时 平摊cost=原cost + 你设 04/28 12:25
4F：→ kaneson: 计的位能变化 04/28 12:25
5F：推 kaneson: 然後这个位能值通常做法是跟你要操作的资料结构用个funct 04/28 13:10
6F：→ kaneson: ion对应成一个值，这样就很容易验证是否满足前提. 而相 04/28 13:11
谢谢解释，原理懂了
但还是无法理解解答那个potential function的为何是那样QQ
7F：→ kaneson: 对记帐法，设计时只需对每个操作绑一个固定值，乍看很简 04/28 13:11
8F：→ kaneson: 单，但若要验证过程中会不会发生总和低於0就比较麻烦。这 04/28 13:11
9F：→ kaneson: 就是位能法比记帐法常用的原因 04/28 13:11
※ 编辑: kronze7109 (42.77.46.4 台湾), 04/28/2021 21:50:01
10F：推 aa871220: 我觉得立宇这个解法有点难懂 04/28 23:16
11F：→ aa871220: 这题是CLRS的习题 你可以找一下amortized cost那章的解 04/28 23:16
12F：→ aa871220: 答 我觉得写得比较好 04/28 23:16
13F：→ aa871220: （有点懒就懒得贴了sorry) 04/28 23:16
谢谢a大
我会找时间去看CLRS的！！
14F：推 kaneson: potential function 其实只要不违背前提可自由发挥, 只是 04/29 09:55
15F：→ kaneson: 得到的cost是否够tight, 课本的stack例子二种做法都有点 04/29 09:55
16F：→ kaneson: 像是不违反前提下把某些操作cost挪给别的操作来保持tight 04/29 09:55
17F：推 kaneson: 这题可用tree node深度加总来当位能, 每个 node 平均深 04/29 09:59
18F：→ kaneson: 度lgn, 增加一个node就总和增加lgn, 少一个node就少lgn. 04/29 09:59
19F：→ kaneson: 用这个来做位能差。网路上有解法是写lg1加到lgn就结束了 04/29 09:59
谢谢k大
後面的计算我有理解出增减一个node都为lgn的cost
但不理解他potential function里面符号的定义
20F：→ kaneson: ,林的写法是在数学上比较严谨 04/29 09:59
※ 编辑: kronze7109 (42.77.46.4 台湾), 04/29/2021 12:52:40
※ 编辑: kronze7109 (42.77.46.4 台湾), 04/29/2021 12:54:05
21F：推 NTUmaki: 去看台大演算法影片教比较清楚 04/30 13:23