Pow(x, n)

Средняя№50степень пополам

Даны число x и целое n, возможно отрицательное. Нужно посчитать x в степени n без готовой функции возведения в степень. Наш пример: x = 2, n = -13 — ответ 1 / 8192 = 0.0001220703125.

50 Pow(x, n)Разбор · 1×

Пример: возвести 2 в степень -13: единица на 2^13, а 2^13 — из 2^6 в квадрате, умноженного на 2.

ждёт в стеке вызововтекущий вызов, потом лишний x нечётного nx^half, посчитан вызовом нижета же половина ещё раз, бесплатно

n = -13 < 0: 2^-13 = 1 / 2^13

01/25
сначала · назад · пуск · шаг
Скорость
1function myPow(x, n):
2 if n < 0:
3 return 1 / power(x, -n)
4 return power(x, n)
5
6function power(x, n):
7 if n == 0:
8 return 1
9 half = power(x, n / 2) // rounded down
10 if n is even:
11 return half * half
12 return half * half * x
состояние
x
2
n
-13
half
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. x^n — это x^(n/2), умноженное само на себя, и ещё один x, если n нечётное: задача для n сводится к одной задаче для половины n.
  2. Половину считаем один раз и умножаем саму на себя, поэтому уровень стоит одного вызова и одного-двух умножений, а n на каждом уровне уменьшается вдвое до 0.
  3. Отрицательное n только переворачивает ответ: x^-n = 1 / x^n.

Сложность

Время O(log n): на каждом вызове n уменьшается вдвое, значит, вызовов около log n, и в каждом не больше двух умножений. Память O(log n): в стеке вызовов по одному вызову на каждое деление пополам.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.