※ 引述《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.