以下计划的复杂性是什么？

Question

以下计划的复杂性是什么？我认为它必须是O(n),因为有一个for循环运行了n次.

它是一个反转给定整数中的位的程序.

unsigned int reverseBits(unsigned int num)
{
    unsigned int NO_OF_BITS = sizeof(num) * 8;
    unsigned 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;
}

上述计划的复杂程度如何？有人说实际的复杂性是O(log n),但我看不出原因.

Answer 1

考虑到你的上述程序,复杂性是O(1)因为8 * sizeof(unsigned int)是一个常数.您的程序将始终以恒定的时间运行.

但是,如果n绑定NO_OF_BITS并且您将该数字作为算法参数(事实并非如此),则复杂性将是O(n).

注意,对于n位,可能的最大值num是2^n,并且在这种情况下,如果要将复杂性表示为允许的最大值的函数num,则复杂性为O(log?(n))或O(log(N)).