Space 反转位的复杂性

Question

此解决方案的 space 复杂度是多少？此代码反转 32 位无符号整数的位。我不确定 space 是否是 O(N) 因为在返回答案之前复制了所有位，或者这是否被认为是 O(1) 因为答案的大小不依赖于大小输入 A.

unsigned int Solution::reverse(unsigned int A) {
  unsigned int ans = 0;
  for (unsigned int i = 0; i < 32 ; ++i) {
      if (A & (1 << i)) {
          ans += (1 << (31-i));
      }
  }
  return ans;
}

Answer 1

你的函数只接受 unsigned int，所以算法受 sizeof (unsigned int) 的限制，所以它总是相同的，所以 O(1)。

Answer 2

如果我们尝试逐行分析您的代码：

unsigned int Solution::reverse(unsigned int A) {
    unsigned int ans = 0;                        // O(1)
    for (unsigned int i = 0; i < 32 ; ++i) {     // O(1)
        if (A & (1 << i)) {                      // O(1)
            ans += (1 << (31-i));                // O(1)
        }
    }
    return ans;
}

你所做的每一个操作都是线性的。它不依赖于您提供的任何参数，因为 unsigned int 具有固定大小。根据我的说法，你的方法是 O(1).

如果我可以建议：您应该避免在代码中对值 32 进行硬编码，并将其替换为 sizeof(A)*8，这应该更便于携带。 sizeof() return 对象的字节大小。更多信息 here.

Space 反转位的复杂性

Space Complexity for Reversing Bits

c++

bit-manipulation

space-complexity