Временная сложность функции обратного бита в C - PullRequest
Новая
       1

Временная сложность функции обратного бита в C

0 голосов
/ 10 октября 2018 
#include <stdio.h>

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

int main()
{
    unsigned int num = 0;
    scanf("%u", &num);
    printf("bit reverse of %u is %u\n", num, reverseBits(num));
    return 0;
}

Какова временная сложность этой функции обращения битов, если мы изменим размер ввода на uint_8 / uint_16 / uint64_t, цикл for будет выполнен для размера ввода * 8 раз.Эта функция работает в постоянное время для n входов.так какова временная сложность этой функции в большой записи "O"?

1 Ответ

0 голосов
/ 10 октября 2018

O (n) для n битов.

Для uint_8 алгоритм выполняется в 8 шагов.
Для uint_16 алгоритм работает в 16 шагах.

и т. Д.

Я не эксперт, но некоторые наборы инструкций могут иметь обратный бит в один цикл (используйте__asm__), поэтому вы можете запустить в O (n) для n байт ;в восемь раз быстрееНекоторые компиляторы могут делать это автоматически, если вы используете -O3.

...