Бинарное возведение в степень
Поговорим сегодня о простой оптимизации, которая называется «бинарное возведение в степень».
Программа
def pow(x, y): result = 1 for i in range(y): result = result * x return result
Однако эта программа неэффективна в терминах вычислительной сложности (в данном случае это число умножений, которое равно O(y)).
Можно улучшить этот показатель, заметив, что:
Теперь, если мы будем вычислять степень, применим такой способ:
Улучшенная программа
def pow(x, y): if y == 0: return 1 tmp = pow(x, y / 2) if y % 2 == 0: # обработка чётного y return tmp * tmp else: # обработка нечётного y return tmp * tmp * x