为什么以下代码的时间复杂度为o(logn)

Question

我试图理解下面代码的时间复杂性.当我尝试自己计算时间复杂度时,它会变成o(n).因为"NO_OF_BITS"对于任何int总是相同的,因此循环不会随输入增加/减少.我不确定在循环内执行的按位操作.任何人都可以帮助我理解/计算此代码的时间复杂度.

    unsigned int reverseBits(unsigned int num)
    {
       int  NO_OF_BITS = sizeof(num) * 8;
       int reverse_num = 0;
       int i;
       for (i = 0; i < NO_OF_BITS; i++)
     {
       if((num & (1 << i)))
         reverse_num |= 1 << ((NO_OF_BITS - 1) - i);  
     }
       return reverse_num;
    }              

Answer 1

根据你的逻辑,代码实际上是O(1)因为NO_OF_BITS永远都是32.

如果你谈论时间复杂度和渐近行为,你必须增加输入大小.这段代码O(NO_OF_BITS)是O(log(num)).

由于函数的输入是num,有意义的是定义n为num,而不是NO_OF_BITS.