Re: [問題] Hw3 2.1
※ 引述《killyou (xxx)》之銘言：
: ※ 引述《starmap (starmap)》之銘言：
: : 請問2.1題目是說 1, 2, 3,... n "全部"可以用 O(n) 空間存(相加)
: : 或 1, 2, 3,... n "分別" 可用 O(n) 空間存?
: : 若是前者似乎是不成立的
: : 如果是後者, 1, 2, 3, ... 似乎描述上有點累贅, 為什麼不是直接說 n 就好了?
: : 感謝回答
: 前者,他是要把 1~n 這 n個數都存起來.
: 當然,直接存是不止 O(n)的.
: m 可以用 1+[lg m] 存 (log_2 m take gauss)
: 直接全部存起來,
: \sum_{m=1}^n 1+[lg m] (直接取和)
: 這樣要O(n lg n),應該不是用這個方法.
: 提示: 利用 de Bruijn sequence.
題意要求實在是沒有很清楚......
是全部要存入，只花O(n)，這裡現在沒問題了
可是，考不考慮取值的方式？
有如這個提示一般，在存入的時候我們對這m個數字做了個特殊方式存入
所以，我們取值的時候可以用特別的方式處理嗎？
(例如說：取出來的值對它做加減運算)
還是只能把取出來的值直接輸出？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.70.75.185
討論串 (同標題文章)