Как рассчитать степень числа со сложностью O (log n)?

Question

Это для чистого понимания, но у меня есть код, который в основном O (n), но я не могу понять, как изменить его на Olog (n), и каждый раз, когда я использую рекурсию, я получаю сложность nlog (n).

def power(n,p):
    val = []
    for i in range(p):
        val.append(n)
    res = val
    n = 1
    for x in res:
        n*= x
    return n
print(power(2,8)) # returns 256

мне нужен код, который делает то же самое, что и код выше, но в основном делает это в Olog (n), а не в O (n)

Answer 1

Этот код реализует power() со сложностью O (log (n)) :

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