Лучший подход для получения числа нулей в двоичной строке

Question

У меня одна двоичная строка, и мне нужно вычислить количество нулей в этой строке

я знаю, что мы можем решить это за линейное время, но я хочу решение с o (k)

где k - количество нулей в строке.

N - длина строки 1 <= N <10 ^ 6 </p>.

Answer 1

Учитывая строку из N независимых битов, вам придется просматривать каждый бит хотя бы один раз. Это дает временную сложность O (N). Невозможно сделать это асимптотически быстрее.

Алгоритмы, приведенные в упомянутых вопросах, предполагают, что вся битовая строка вписывается в слово и может обрабатываться в O (1). Это не выполняется, если строка может быть произвольно длинной.

Answer 2

Вы можете использовать алгоритм Хэмминга , на самом деле вычислить расстояние Хэмминга строки, затем subtract из размера вашей двоичной строки (N)