Временная сложность
Лучший: O(log n)
Средний: O(log n)
Худший: O(log n)
Быстрое возведение в степень позволяет вычислить aⁿ за O(log n), деля показатель степени пополам на каждом шаге вместо того, чтобы умножать a само на себя n раз.
Как это работает:
1. Базовый случай: a⁰ = 1
2. Рекурсивно вычисляем half = binPow(base, floor(exp / 2))
3. Если exp чётное, возвращаем half × half
4. Если exp нечётное, возвращаем half × half × base
Почему это быстро:
Каждый рекурсивный вызов делит показатель степени пополам, поэтому глубина рекурсии пропорциональна log₂ n, а не n.
Временная сложность:
Лучшая: O(log n)
Средняя: O(log n)
Худшая: O(log n)
Пространственная сложность: O(log n) из-за стека рекурсивных вызовов
Применение:
- Модульное возведение в степень в криптографии
- Быстрое возведение матриц в степень
- Соревновательное программирование и теория чисел
Главная идея заключается в повторном использовании степеней: зная a^(n/2), можно возвести результат в квадрат и сразу получить большую часть нужного результата.
Похожие алгоритмы
Частые вопросы
- Что такое Быстрое возведение в степень?
- Быстрое возведение в степень позволяет вычислить aⁿ за O(log n), деля показатель степени пополам на каждом шаге вместо того, чтобы умножать a само на себя n раз.
- Какова сложность Быстрое возведение в степень?
- Время (среднее): O(log n) · Память: O(log n)
- Для кого предназначена визуализация Быстрое возведение в степень?
- Визуализация Быстрое возведение в степень рассчитана на средний уровень в категории «Разделяй и властвуй». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Быстрое возведение в степень?
- В той же категории (Разделяй и властвуй) вы можете изучить: Tower of Hanoi. Каждый из них имеет интерактивную визуализацию.