Power Function Python

Question

이 함수는 a^b의 값을 계산하여 그것을 반환합니다. m = log (b) 경우 가장 좋은 경우 시나리오는 m + 1 상호 작용 이지만 최악의 경우는 무엇입니까? ? while 루프에 몇 번이나 들어 갑니까?

def power(a,b): 
    result=1 
    while b>0: # b is nonzero 
     if b % 2 == 1: 
      result=result*a 
     a=a*a 
     b = b//2 
    return result 

Answer 1

@EliSadoff이 코멘트에 명시된 바와 같이, 당신은 당신의 기능에 result의 초기 값이 필요합니다. 줄을 삽입

result = 1 

def 줄 바로 뒤에. 그런 다음 코드가 작동하며 이는 암시 적으로 b의 이진 표현을 사용하여 지수를 빠르게 얻는 표준 방법입니다. (루프 불변는 result * a ** b의 값이 알고리즘의 유효성을 표시하는 일정하게 유지된다.)하여 if b % 2 라인이 while 루프를 통해마다 실행된다

최악이다. b이 2의 거듭 제곱보다 작은 경우마다 발생하며 따라서 b의 모든 숫자는 1입니다. while 루프 조건 while b>0은 여전히 ​​m+1 번만 검사되지만 각 루프는 이제 할 일이 조금 더 있습니다.

코드 속도를 높이는 방법에는 여러 가지가 있습니다. if b % 2 = 1 대신 while b>0 및 if b & 1 대신 while b을 사용하십시오. b = b // 2 대신 a = a*a 및 b >>= 1 대신 result = result*a 및 a *= a 대신 result *= a을 사용하십시오. 물론 이것은 상당히 사소한 개선입니다. 루프를 더 빠르게하는 유일한 방법은 구조화되지 않은 코드를 사용하는 것입니다. 파이썬에서는 가능하지 않습니다. (필요 이상으로 a의 수정이 더 많이 있지만 루프에 점프하지 않고이를 방지하는 좋은 방법은 없습니다.) 내부 루프를 수정하는 등이 코드에는 몇 가지 변형이 있습니다 (예 : a 및 b). b은 짝수이지만 항상 빠를 수는 없습니다.

는

최종 코드는 내가 코드를 정리

def power(a, b): 
    """Return a ** b, assuming b is a nonnegative integer""" 
    result = 1 
    while b: 
     if b & 1: 
      result *= a 
     a *= a 
     b >>= 1 
    return result 

다음이다 PEP8 (파이썬 스타일 기준) 더 잘 맞는에 조금. 특히 b이 음이 아닌 정수인지 확인하기 위해 코드를 검사하는 데 오류가 없다는 점에 유의하십시오. b이 음의 정수인 경우 내 코드가 무한 루프가된다고 생각하며 잘못된 결과를 반환합니다. 그러니 오류 체크를하십시오! 또한 당신의 코드가 그러한 기능을위한 꽤 표준 인 power(0, 0) == 1을 말하지만 여전히 놀랍게도 어떤 사람들은 걸립니다.