[問題] 資料結構 陣列

[aleelyle (lyle)]

        ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
             ( 未必需要依照此格式，文章條理清楚即可 )

遇到的問題： (題意請描述清楚)

某個學校的考古題.....
一個size是N的陣列 有以下的operations
1>initial()
2>write(k,m)
3>read<k>
4>multiplyall(n) 所有陣列的元素乘以n

條件: 除了 1> 以外, 其他的operations  time 的 worst case 都是O(1)
實作這個陣列

1>, 2>, 3> 我可以輕易的做出來
有問題的是4> 我想了很久還是不知道該怎麼讓running time = O(1)
原始的方法是用for or while將每個元素走過1次

i=N;
while(i-- >= 0>{
e = read<i>;
write<i, e*n>;
}

但是這樣的running time 是 O(N>

希望有人能幫我指引一下方向..... 感謝

原文 第一題
http://homepage8.seed.net.tw/web@5/aleelyle/971.pdf

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.105.45.204
※ aleelyle:轉錄至看板 Programming                                 02/23 13:44
推 ledia:設一個 global 的乘積值, 輸出前乘過一次就好
→ ledia:讀進來的時候也要先除一次, 維持 consistency
→ ledia:還有一些細節, 比如說全部乘以 n 之後再讀一個數字進來
→ ledia:其中 n = 0
→ aleelyle:這我也想過 但是這樣做過這個operator後 真正存在電腦中
→ aleelyle:的資料是不正確的
推 VictorTom:1>跟4>同屬要對所有aray elements都設值的處理, 4>是要
→ VictorTom:怎樣可以做到O(1)....?_?
→ VictorTom:在I/O的時候動手腳的話感覺很糟, 而且本質上嘛....@_@"
※ 編輯: aleelyle        來自: 59.104.191.117       (02/23 14:23)
※ 編輯: aleelyle        來自: 59.105.45.136        (02/23 15:11)
→ MOONRAKER:存在電腦中資料不正確有什麼關係
→ MOONRAKER:反正不read也無從得知陣列裡是什麼 那就保證read出來
→ MOONRAKER:會正確，不就結了
→ MOONRAKER:除非他再定義不用read就得知內容的peep(k)和peepall()
推 VictorTom:雖然M大說的沒錯, 但是加上後面那個ZEROALL()要O(1)的考
→ VictorTom:題, 小弟還是覺得這種考題滿鳥的; 而且儲存的資料不保證
→ VictorTom:正確要靠I/O filter的資料結構, 不曉得可以怎麼利用@_@"
→ MOONRAKER:啊！有zeroall()喔
→ MOONRAKER:我怎麼覺得這好像在設計一個電路 不是寫程式了
推 VictorTom:忽然覺得ZeroAll()應該不是小弟想的用MulAll 0做, 不然
→ VictorTom:後面WRITE->READ應該會有問題; 不曉得可以怎麼做說@_@"
推 Fenikso:這只是在考理論 不要用程式設計的角度看它
推 Ag2S:把Global乘積改成list如何? read/write時再乘 並記錄已經乘到
→ Ag2S:哪一個了 ZeroAll也可以直接用*0來做了
→ Ag2S:不過 read/write的時間複雜度就depend on MultiplyAll()了
→ Ag2S:阿 我指MultiplyAll被呼叫過幾次
推 ledia:其實這種 filter 的例子很多呀, 像是 3d rendering 的
→ ledia:transpose matrix
→ jhchou:我覺得這考題很好啊 考你怎麼設計一個資料結構來降低需要
→ jhchou:大量使用到的指令的複雜度
推 loveme00835:這叫lazy evaluation 不需要的, 就不要去算他