存储整数二进制表示的空间复杂度：O(logn)还是O(1)？

这个问题的答案得看输入整数的范围是否有固定限制，分两种情况说：

• 无固定范围的整数（比如支持任意精度的大整数）
  这种情况下，整数n的二进制位数确实和log₂n成正比——数值越大，需要的二进制位数越多，存储空间会随着n的增大而增长。所以此时算法的空间复杂度是O(logn)。

• 输入有固定范围限制（比如32位有符号整数、64位无符号整数这类硬件/语言限定的固定长度类型）
  不管输入的n是这个范围内的最小值还是最大值，二进制表示的长度上限是固定的（比如32位整数最多需要32位二进制位，算上符号位也不会超过固定值）。此时需要的存储空间是一个固定常数，不会随输入n的大小变化而改变，所以空间复杂度是O(1)。

简单总结：空间复杂度的核心是看「随着输入规模增长，空间需求的变化趋势」——如果输入规模被固定死了（比如只能是32位整数），那空间需求就是常数级；如果输入可以无限大，那空间需求就跟着logn走。

内容的提问来源于stack exchange，提问作者marcusdel2112