Блог

Основная оптимизация, которую вы должны использовать здесь, — это устранение общих вложенных выражений. Рассмотрим ваш первый фрагмент кода:

 def power(x, y):
    if y == 0: 
        return 1
    elif y % 2 == 0:
        return (power(x, y // 2) * power(x, y // 2)
    else:
        return (x * power(x, y // 2) * power(x, y // 2)
 

Я немного очистил его — так y как это an int , y % 2 также будет an int , и, таким образом, нет необходимости преобразовывать типы. И канонический способ написания int(y / 2) таков y // 2 . Наконец, в if while операторах и нет необходимости заключать логическое предложение в круглые скобки, поскольку мы заканчиваем предложение точкой с запятой (тогда как в синтаксисе, подобном C, возможно наличие if оператора в 1 строку, и поэтому нам нужны круглые скобки).

Проблема здесь в том, что вы вычисляете power(x, y // 2) дважды как elif в том, так и в else другом случае. Вместо этого вы должны попытаться вычислить это значение только один раз.

 def power(x, y):
    if (y == 0): 
        return 1
    else:
        smaller_power = power(x, y // 2)
        if y % 2 == 1:
            return x * smaller_power * smaller_power
        else:
            return smaller_power * smaller_power
 

Это немедленно и значительно повышает эффективность вашего алгоритма. Вместо того, чтобы быть O(y) вовремя, улучшенная версия находится O(log y) во времени (предполагая, что мы считаем одну * операцию как 1).

Проявив немного сообразительности, мы можем придумать немного другой алгоритм:

 def power(x, y):
    if y == 0:
        return 1
    else:
        smaller_power = power(x * x, y // 2)
        return x * smaller_power if y % 2 == 1 else smaller_power
 

который может быть преобразован в следующую хвостовую рекурсивную версию:

 def power_tail_helper(x, y, acc):
    """
    returns acc * power(x, y)
    """
    if y == 0:
        return acc
    else:
        new_acc = acc * x if y % 2 == 1 else acc
        return power_tail_helper(x * x, y // 2, new_acc)

def power_tail(x, y):
    return power_tail_helper(x, y, 1)
 

что, в свою очередь, может быть превращено в следующий итерационный алгоритм:

 def power_iter(x, y):
    acc = 1
    while y != 0:
        (x, y, acc) = (x * x, y // 2, acc * x if y % 2 == 1 else acc)
    return acc
 

Обратите внимание, что в идиоматическом Python мы бы вместо этого написали это как

 def power_iter(x, y):
    acc = 1
    while y:
        x, y, acc = (x * x, y // 2, acc * x if y % 2 else acc)
    return acc
 

используя тот факт, что числа автоматически преобразуются в логические значения в соответствующем контексте, при этом 0 равно False , а все остальные числа равны True .

Последний подход, который вы могли бы использовать, является более математическим. Вы можете вычислить показатель степени, используя логарифмы. Для получения точного ответа потребуется высокоточная библиотека логарифмов, поскольку base это 320-разрядное число, слишком большое для обычной 64-разрядной арифметической версии с плавающей запятой двойной точности log , чтобы быть достаточно точным. Это, вероятно, оптимальный подход, но вам придется провести больше исследований.

В любом случае, имейте в виду, что размер выходных данных будет числом, для хранения которого потребуется более 100 миллионов байт. Поэтому независимо от того, какой алгоритм вы используете, это займет некоторое время, так как даже «алгоритм» сохранения ответа в памяти и его считывания займет некоторое время.