PTT數位生活區 / C_and_CPP (C/C++)

[問題] 資料結構 陣列

看板C_and_CPP (C/C++)作者 (lyle)時間16年前 (2010/02/23 13:33), 編輯推噓8(8推 0噓 22→)
留言30則, 8人參與, 最新討論串1/2 (看更多)
( *[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
推
02/23 13:45, , 1F
設一個 global 的乘積值, 輸出前乘過一次就好
02/23 13:45, 1F
→
02/23 13:45, , 2F
讀進來的時候也要先除一次, 維持 consistency
02/23 13:45, 2F
→
02/23 13:46, , 3F
還有一些細節, 比如說全部乘以 n 之後再讀一個數字進來
02/23 13:46, 3F
→
02/23 13:46, , 4F
其中 n = 0
02/23 13:46, 4F
→
02/23 13:53, , 5F
這我也想過 但是這樣做過這個operator後 真正存在電腦中
02/23 13:53, 5F
→
02/23 13:54, , 6F
的資料是不正確的
02/23 13:54, 6F
推
02/23 14:12, , 7F
1>跟4>同屬要對所有aray elements都設值的處理, 4>是要
02/23 14:12, 7F
→
02/23 14:12, , 8F
怎樣可以做到O(1)....?_?
02/23 14:12, 8F
→
02/23 14:14, , 9F
在I/O的時候動手腳的話感覺很糟, 而且本質上嘛....@_@"
02/23 14:14, 9F
※ 編輯: aleelyle 來自: 59.104.191.117 (02/23 14:23) ※ 編輯: aleelyle 來自: 59.105.45.136 (02/23 15:11)
→
02/23 15:12, , 10F
存在電腦中資料不正確有什麼關係
02/23 15:12, 10F
→
02/23 15:13, , 11F
反正不read也無從得知陣列裡是什麼 那就保證read出來
02/23 15:13, 11F
→
02/23 15:13, , 12F
會正確，不就結了
02/23 15:13, 12F
→
02/23 15:14, , 13F
除非他再定義不用read就得知內容的peep(k)和peepall()
02/23 15:14, 13F
推
02/23 16:15, , 14F
雖然M大說的沒錯, 但是加上後面那個ZEROALL()要O(1)的考
02/23 16:15, 14F
→
02/23 16:16, , 15F
題, 小弟還是覺得這種考題滿鳥的; 而且儲存的資料不保證
02/23 16:16, 15F
→
02/23 16:17, , 16F
正確要靠I/O filter的資料結構, 不曉得可以怎麼利用@_@"
02/23 16:17, 16F
→
02/23 16:18, , 17F
啊！有zeroall()喔
02/23 16:18, 17F
→
02/23 16:18, , 18F
我怎麼覺得這好像在設計一個電路 不是寫程式了
02/23 16:18, 18F
推
02/23 16:21, , 19F
忽然覺得ZeroAll()應該不是小弟想的用MulAll 0做, 不然
02/23 16:21, 19F
→
02/23 16:22, , 20F
後面WRITE->READ應該會有問題; 不曉得可以怎麼做說@_@"
02/23 16:22, 20F
推
02/23 16:25, , 21F
這只是在考理論 不要用程式設計的角度看它
02/23 16:25, 21F
推
02/23 16:33, , 22F
把Global乘積改成list如何? read/write時再乘 並記錄已經乘到
02/23 16:33, 22F
→
02/23 16:34, , 23F
哪一個了 ZeroAll也可以直接用*0來做了
02/23 16:34, 23F
→
02/23 16:34, , 24F
不過 read/write的時間複雜度就depend on MultiplyAll()了
02/23 16:34, 24F
→
02/23 16:35, , 25F
阿 我指MultiplyAll被呼叫過幾次
02/23 16:35, 25F
推
02/23 16:37, , 26F
其實這種 filter 的例子很多呀, 像是 3d rendering 的
02/23 16:37, 26F
→
02/23 16:38, , 27F
transpose matrix
02/23 16:38, 27F
→
02/23 16:38, , 28F
我覺得這考題很好啊 考你怎麼設計一個資料結構來降低需要
02/23 16:38, 28F
→
02/23 16:39, , 29F
大量使用到的指令的複雜度
02/23 16:39, 29F
推
02/23 18:44, , 30F
這叫lazy evaluation 不需要的, 就不要去算他
02/23 18:44, 30F
‣ 更多 aleelyle 的文章
文章代碼(AID): #1BWsYKSp (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 aleelyle 的文章
文章代碼(AID): #1BWsYKSp (C_and_CPP)