0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: алгоритмы для разработчиков, бинарное возведение, степень</p>
1
<p>Теги: алгоритмы для разработчиков, бинарное возведение, степень</p>
2
<p>Поговорим сегодня о простой оптимизации, которая называется "бинарное возведение в степень".</p>
2
<p>Поговорим сегодня о простой оптимизации, которая называется "бинарное возведение в степень".</p>
3
<p>Для начала просто сделаем цикл, который вычисляет степень<em>"в лоб"</em>простым перемножением y раз.</p>
3
<p>Для начала просто сделаем цикл, который вычисляет степень<em>"в лоб"</em>простым перемножением y раз.</p>
4
<h2>Программа</h2>
4
<h2>Программа</h2>
5
def pow(x, y): result = 1 for i in range(y): result = result * x return result<p>Однако эта программа неэффективна в терминах вычислительной сложности (в данном случае это число умножений, которое равно<strong>O(y)</strong>).</p>
5
def pow(x, y): result = 1 for i in range(y): result = result * x return result<p>Однако эта программа неэффективна в терминах вычислительной сложности (в данном случае это число умножений, которое равно<strong>O(y)</strong>).</p>
6
<p>Можно улучшить этот показатель, заметив, что:</p>
6
<p>Можно улучшить этот показатель, заметив, что:</p>
7
<p>где [y/2] это y/2, округлённое вниз до целого, то есть наибольшее целое число, меньшее или равное y/2. Например, [20/2] = 10, [7/3]=2.</p>
7
<p>где [y/2] это y/2, округлённое вниз до целого, то есть наибольшее целое число, меньшее или равное y/2. Например, [20/2] = 10, [7/3]=2.</p>
8
<p>Теперь, если мы будем вычислять степень, применим такой способ: Если y нечётное, применим аналогичную схему:</p>
8
<p>Теперь, если мы будем вычислять степень, применим такой способ: Если y нечётное, применим аналогичную схему:</p>
9
<h2>Улучшенная программа</h2>
9
<h2>Улучшенная программа</h2>
10
def pow(x, y): if y == 0: return 1 tmp = pow(x, y / 2) if y % 2 == 0: # обработка чётного y return tmp * tmp else: # обработка нечётного y return tmp * tmp * x<p><em>Есть вопрос? Напишите в комментариях!</em></p>
10
def pow(x, y): if y == 0: return 1 tmp = pow(x, y / 2) if y % 2 == 0: # обработка чётного y return tmp * tmp else: # обработка нечётного y return tmp * tmp * x<p><em>Есть вопрос? Напишите в комментариях!</em></p>
11
11