Reduce time /space complexity of simple loop-CodePudding

So basically if i have an iteration like this in python Ive editted the question to include my full code

class Solution:
    def myPow(self, x: float, n: int) -> float:
        temp = [];
        span = range(1,abs(n))
        if n ==0:
            return 1
        if abs(n)==1:
            temp.append(x)
        else:
            for y in span:
                if y == 1:
                    temp = []
                    temp.append(x*x)
                else:
                    temp.append(temp[-1] * x)
        if(n < 0):
            return 1/temp[-1]
        else:
            return temp[-1]

The problem link is : Pow(x,n)-leetcode How can I modify this to conserve memory and time. Is there another data structure i can use. Im just learning python....

------------EDIT------------ ive modified the code to use a variable instead of a list for the temp data

class Solution:
    def myPow(self, x: float, n: int) -> float:
        span = range(1,abs(n))
        if n ==0:
            return 1
        if abs(n)==1:
            temp = x
        else:
            for y in span:
                if y == 1:
                    temp = x*x
                else:
                    temp = temp * x
        if(n < 0):
            return 1/temp
        else:
            return temp

I still have a problem with my time complexity. Its working for many testcases, however when it trys to run with x = 0.00001 and n = 2147483647. The time limit issue arises

CodePudding user response：

To reduce the time complexity you can divide the work each time by taking x to the power of 2 and dividing the exponent by two. This makes a logarithmic time algorithm since the exponent is halved at each step.

Consider the following examples:

10^8 = 10^(2*4) = (10^2)^4 = (10*10)^4

Now, there is one edge case. When the exponent is an odd number you can't integer divide it by 2. So in that case you need to multiply the results by the base one additional time.

The following is a direct recursive implementation of the above idea:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        sign = -1 if n < 0 else 1
        n = abs(n)
        
        def helper(x, n):
            if n == 1: return x
            if n == 0: return 1
            
            if n % 2 == 1:
                return helper(x*x, n // 2) * x
            else:
                return helper(x*x, n // 2)
        
        res = helper(x, n)
        if sign == -1:
            return 1/res
        else:
            return res

Note that we have taken abs of the exponent and stored the sign and deal with it at the end.

CodePudding user response：

Instead of iterating from 1 to n, use divide-and-conquer: divide the exponent by 2 and use recursion to get that power, and then square that result. If n was odd, multiply one time more with x:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n == 1:
            return x
        if n < 0:
            return self.myPow(1/x, -n)
        temp = self.myPow(x, n // 2)
        temp *= temp
        if n % 2:
            temp *= x
        return temp

CodePudding user response：

A simple naive solution might be:

def myPow(x: float, n: int) -> float:
    ## -----------------------
    ## if we have a negative n then invert x and take the absolute value of n
    ## -----------------------
    if n < 0:
        x = 1/x
        n = -n
    ## -----------------------

    retval = 1
    for _ in range(n):
        retval *= x
    return retval

While this technically works, you will wait until the cows come home to get a result for:

x = 0.00001 and n = 2147483647

So we need to find a shortcut. Lets' consider 2^5. Our naïve method would calculate that as:

(((2 * 2) * 2) * 2) * 2 == 32

However, what might we observe about the problem if we group some stuff together in a different way:

(2 * 2) * (2 * 2) * 2 == 32

similarly:

((2 * 2) * (2 * 2) * 2) * ((2 * 2) * (2 * 2) * 2) == 32 * 32 = 1024

We might observe that we only technically need to calculate

(2 * 2) * (2 * 2) * 2 == 32

once and use it twice to get 2^10.

Similarly we only need to calcuate:

2 * 2 = 4

once and use it twice to get 2^5....

This suggests a recursion to me.

Let's modify our first attempt to use this divide and concur method.

def myPow2(x: float, n: int) -> float:
    ## -----------------------
    ## if we have a negative n then invert x and take the absolute value of n
    ## -----------------------
    if n < 0:
        x = 1/x
        n = -n
    ## -----------------------

    ## -----------------------
    ## We only need to calculate approximately half the work and use it twice
    ## at any step.
    ## -----------------------
    def _recurse(x, n):
        if n == 0:
            return 1
        res = _recurse(x, n//2) # calculate it once
        res = res * res # use it twice
        return res * x if n % 2 else res # if n is odd, multiple by x one more time (see 2^5 above)
    ## -----------------------

    return _recurse(x, n)

Now let's try:

print(myPow2(2.0, 0))
print(myPow2(2.0, 1))
print(myPow2(2.0, 5))
print(myPow2(2.1, 3))
print(myPow2(2.0, -2))
print(myPow2(0.00001, 2147483647))

That gives me:

1
2.0
32.0
9.261000000000001
0.25
0.0

CodePudding user response：

If you have to loop, you have to lope and there is nothing that can be done. Loops in python are slow. That said you may not have to loop and if you do have to loop, it may be possible to push this loop to a highly optimised internal function. Tell us what you are trying to do (not how you think you have to do it, appending elements to a lis may or may not be needed). Always recall the two rules of program optimisation General Rule: Don't do it. Rule for experts: Don't do it yet. Make it work before you make it fast, who knows, it may be fast enough.