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