上限固定时的操作顺序

Question

我最近接受了采访,并被要求查找提供的整数位数.我有这样的事情:

#include <iostream>

using namespace std;
int givemCountOnes (unsigned int X) {
  int count =0;
  while (X != 0 ) {
    if(X & 1)
      count++;
   X= X>>1;
  }

 return count;

}

int main() {
cout << givemCountOnes (4);
return 0;
}

我知道有更好的方法,但这不是问题.

问题是,这个程序的复杂性是什么？

由于它是输入中的位数,人们说这是O(n),其中n是输入中的位数.

但是我觉得既然上限sizeof(unsigned int)就是说64位,我应该说顺序是o(1).

我错了吗？

Answer 1

复杂性是O(N).复杂性随着所用类型(unsigned int)的大小线性增加.

上限无关紧要,因为它可以在将来的任何时间延长.它也无关紧要,因为总有一个上限(内存大小,宇宙中的原子数),然后一切都可以被认为是O(1).