В чем разница между следующими двумя решениями голосовой строки leetcode Pow (x, n)

Question

Я работаю над вопросом №50 LeetCode с именем Pow (x, n) (https://leetcode.com/problems/powx-n/). Он попросил меня вернуть n силу x. Ниже мое первоначальное решение о разделении и победе.

public class Solution { 
public double myPow(double x, int n) { 
    if(n == 1) {return x;} 
    if(n == 0) {return 1;} 
    if(x == 0) {return 0;} 
    if(x == 1) {return 1;} 


    if(n>0) 
    { 
     if(n%2 == 1) 
     { 
      return (myPow(x,n/2)*myPow(x,n/2)*x); 
     } 
     else 
     { 
      return (myPow(x,n/2)*myPow(x,n/2)); 
     } 
    } 
    else if((n<0)&&(n>Integer.MIN_VALUE)) 
    { 
     return (1/myPow(x,-n)); 
    } 
    else return (1/(x*myPow(x,-n-1))); 


    } 
} 

Проблема в том, что при очень большом n это решение имеет проблему с превышением лимита времени. Однако, если изменить код к следующему, время Превышен предел проблема решена:

public class Solution { 
public double myPow(double x, int n) { 
    if(n == 1) {return x;} 
    if(n == 0) {return 1;} 
    if(x == 0) {return 0;} 
    if(x == 1) {return 1;} 


    if(n>0) 
    { 
     if(n%2 == 1) 
     { 
      double sub = myPow(x,n/2); 
      return sub*sub*x; 
     } 
     else 
     { 
      double sub = myPow(x,n/2); 
      return sub*sub;   } 
    } 
    else if((n<0)&&(n>Integer.MIN_VALUE)) 
    { 
     return (1/myPow(x,-n)); 
    } 
    else return (1/(x*myPow(x,-n-1))); 


} 
} 

Почему присвоения значения суб-результата может решить Лимит времени Превышен проблема? В чем разница?

Answer 1

Поскольку JVM не знает, что ваши две myPow (x, n/2) будут делать то же самое, поэтому он будет вычислять его дважды. Присвоение его локальной переменной удаляет это пенитенциарное действие, поэтому ваше время выполнения примерно равно . Недостаток сокращен до 1/2^n раз. Тогда больше нет таймаута.