3622
правки
Изменения
→Двоичный счётчик
Теперь воспользуемся для анализа методом усреднения.
Каждый следующий бит изменяет своё значение в <tex dpi = "150">n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots</tex> операциях.
Общая стоимость: <tex dpi = "150"> \sum\limits_{i=0}^{\lfloor \log n \rfloor} \genfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex>;
<tex dpi = "150"> \genfrac{}{}{}{}{O(n)}{n} = O(1) </tex>
