Proglib.academy | IT-курсы

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

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

🔵 Базовый способ:
— Умножаем число само на себя 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 #буст

Please open Telegram to view this post

VIEW IN TELEGRAM

www.tgoop.com/proglib_academy/2727

317 viewsApr 24 at 12:00

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

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

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

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

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