숫자에 전원을 공급하기위한 측정 복잡성

Question

나누기 및 정복 기법을 사용하여 숫자에 전원을 공급하는 프로그램을 구현했습니다 (^ n).

버전 1 :

def input_params(): 
    a=input('Input \'a\' & \'n\' for a^n:') 
    n=input('') 
    result=power(a,n) 
    print (result) 

def power(a,n): 
    if n<=1: 
     return a 

    elif n%2==0: 
     return pow(power(a,n/2),2) 

    else: 
     return pow(power(a,(n-1)/2),2)*a 

    if __name__ == "__main__": 
    input_params() 

버전 2

def input_params(): 
    a=input('Input \'a\' & \'n\' for a^n:') 
    n=input('') 
    result=power(a,n) 
    print (result) 

def power(a,n): 
    if n<=1: 
     return a 

    elif n%2==0: 
     return power(a,n/2)*power(a,n/2) 

    else: 
     return power(a,(n-1)/2)*power(a,(n-1)/2)*a 



if __name__ == "__main__": 
    input_params() 

버전 3

def input_params(): 
    a=input('Input \'a\' & \'n\' for a^n:') 
    n=input('') 
    result=power(a,n) 
    print (result) 

def power(a,n): 
    if n<=1: 
     return a 

    elif n%2==0: 
     return square(power(a,n/2)) 

    else: 
     return square(power(a,(n-1)/2))*a 

def square(num): 
    return num*num 

if __name__ == "__main__": 
    input_params() 

,536,913 난 같은 문제의 두 버전을 구현

Q1 : 위 버전 중 어느 것이 복잡합니까? θ(lg n)?

질문 2 : 버전 2의 복잡도가 θ(lg n) 인 경우 왜 그럴까요? 버전 2의 문제 크기가 2로 나뉘어지기는하지만 하위 문제의 수가 2이기 때문에 버전 2는 θ(nlg n) 순으로 늘어날 것입니다.

나는 내 결론을 확신하지 못합니다. 사용자가 정의한 적이 pow라는 함수를 사용할 때 하나는 정말 복잡성이 무엇인지 말할 수

감사 버전 1에서

Answer 1

는 아무 대답이 없다.

버전 2에는 중복 계산이 있으므로 이러한 중복 계산을 복잡성의 일부로 간주할지 (쉽게 제외 할 수 있는지) 여부에 따라 답이 달라집니다.

는 square라는 함수의 관점에서 버전 3을 작성 시도하고 당신이 사용하는 기본 작업 (*, / 및 +)의 비용에 대한 몇 가지 가정을 필요로하는 모든 경우에 square

에 대한 정의를 포함한다. 당신은 아마 모든 비용이 O (1)라고 가정하고 싶지만, 분석에서이를 분명히해야합니다.