다음 두 가지 leetcode 퍼즐 솔루션의 차이점은 무엇입니까?

Question

Pow (x, n) (https://leetcode.com/problems/powx-n/)라는 LeetCode 질문 No.50에 대한 연구 중입니다. 그것은 x의 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) 
     { 
      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 시간으로 단축됩니다. 더 이상 시간 제한이 없습니다.