Как уменьшить временную сложность следующего кода Python?

Question

Похоже, что текущая сложность памяти равна O (1), а сложность времени - O (k).Как сохранить сложность памяти на уровне O (1), но уменьшить сложность времени до O (log k)?

import math


# for loop includes k/2 (ie. if k/2 = 3.5, then i will go from [1, 3]. 1,2, and 3
def findPower(x,k):
    y =1
    m = math.trunc(k/2)
    if k == 0:
        return 1
    for i in range(1,m+1):
        y = y * x
    if(k%2 == 0):
        return y * y
    else:
        return y*y*x

Answer 1

Вам нужен алгоритм быстрой мощности , но вам, вероятно, нужен цикл для его правильной реализации (вместо простых if s):

def fast_power(e, p):
    current = e
    result = 1
    while p > 0:
        if p % 2 == 1:
            result *= current
        p = p // 2
        current *= current
    return result