📈 Быстрое возведение числа в целую степень: алгоритм для новичков

Как компьютеры возводят числа в степень эффективно

🔵 Базовый способ:
— Умножаем число само на себя n раз.
— Просто, но медленно: O(n) операций.

def pow_naive(x, n):
result = 1
for _ in range(n):
result *= x
return result

🔵 Быстрый способ: возведение в степень через деление пополам (алгоритм "быстрого возведения в степень"):
— Сокращаем количество операций до O(log n)!
— Идея:
▪️ Если степень чётная → делим пополам.
▪️ Если нечётная → уменьшаем на 1 и снова работаем.

def fast_pow(x, n):
result = 1
while n > 0:
if n % 2 == 1:
result *= x
x *= x
n //= 2
return result

🔵 Чтобы знать об алгоритмах все, забирайте наш курс «Алгоритмы и структуры данных»

Proglib Academy #буст