Re: [理工] [DS]-98交大

[FRAXIS (喔喔)]

※ 引述《ChrismasTick (sdas)》之銘言：
: 請問一下98交大資結演算法最後一題的Amortized analysis要怎麼解呀
: 爬文之後
: 好像書上有公式
: 不過第二小題還是不太會代入
: 有人有寫出答案或是解釋嗎
: http://www2.lib.nctu.edu.tw/n_exam/exam98/cslz/cslz1001.pdf

ci' = ci + φ(Di) - φ(Di-1)
    = i + 2i - 2(i-1) - (2(i-1) - (i-1)),       if i-1 is power of 2
      1 + 2i - 2^(lgi)- (2(i-1) - (2^(lgi-1))), otherwise
    = 3

帶進去展開，只要有耐心就可以得到答案..

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.119.162.50
推 ChrismasTick:不過兩個不同條件式帶出來的值不一樣耶 一個是3一個
→ ChrismasTick:是2!?
→ assassin88:其中一個不是2喔= ="
推 Lautreamont:都是3
推 assassin88:所以是兩個都是三嗎?? 但題目不是說兩個case~
推 Lautreamont:對 奇怪的是我分兩個case討論完答案居然都是3
→ FRAXIS:分兩個Case討論出來都是3阿，這就是答案..
推 ChrismasTick:otherwise那個展開不是1+2i-i-(2(i-1)-(i-1))=2嗎?
→ ChrismasTick:還是我哪邊出錯了
→ FRAXIS:後面那個是2^lg(i-1) 因為ceil在BBS上打不出來 請對照題目
推 ChrismasTick:可是2^lg(i-1)不是等於i-1嗎
→ FRAXIS:有ceil.. 樓上你可以自己帶i-1不是2的次方數的數字進去..
推 ChrismasTick:我懂你的意思了 謝謝幫忙解題
推 ChrismasTick:不過現在我發現我第一個公式代不出來耶
→ ChrismasTick:1 + 2i - 2^(lgi)- (2(i-1) - (2^(lgi-1)))
→ ChrismasTick:i + 2i - 2^(lgi)- (2(i-1) - (2^(lgi-1)))
→ ChrismasTick:怎麼化簡成i + 2i - 2(i-1) - (2(i-1) - (i-1))
→ FRAXIS:把i-1是2的次方數帶進去.. 多帶幾個你就知道為什麼..