※ 引述《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.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.231.114