Здравствуйте, cppguard, Вы писали:

L>>В первой последовательности бинарным поиском в интервале [0,M) находим индекс K первой единицы.
L>>Проверяем значение, находящемся по этому индексу K в следующей последовательности. Если там 0, то берем следующую последовательность, если тоже 1, то ищем индекс K в этой последовательности на отрезке [0, K]. Повторяем (N раз), пока последовательности не закончатся.

C>Ага, и сложность вышеописанного алгоритма — O(N * log(M)) в худшем случае:

C>

C>0 0 ... 0 0 1
C>0 0 ... 0 1 1
C>.............
C>1 1 ... 1 1 1
C>

Мне кажется, что вот такая последовательность должна быть хуже:

0 0 ... 0 0 1
0 0 ... 0 0 1
.............
0 0 ... 0 0 1

Ведь тогда на шагах со второго по последний нам придется делать одинаковые поиски со сложностью O(log(M-1)). Разве нет?