Mess Komplexität für den Antrieb von einer Reihe

Question

I implementiert ein Programm zum Versorgen eine Anzahl (a ^ n) unter Verwendung der Teile und Herrsche-Technik. i implementiert zwei Versionen des gleichen Problems:

Version 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()

Version 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()

Version 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()

Q1: Welche der oben genannten Versionen haben eine Komplexität von θ(lg n)?

Q2: Wenn die Version 2, die Komplexität des θ(lg n) hat, warum? Denn obwohl die Problemgröße in Version 2 durch zwei geteilt wird, ist die Anzahl der Teilprobleme auch zwei, so fühle ich mich Version 2 in der Größenordnung von θ(nlg n) wachsen wird.

Ich bin nicht sicher über meine Schlussfolgerung.

Danke

Answer 1

In der Version 1 gibt es keine Antwort, wie Sie eine Funktion namens pow verwenden, die Sie nie definieren, so dass man nicht wirklich sagen, was die Komplexität ist.

In der Version 2 gibt es redundante Berechnungen, so dass die Antwort davon ab, ob Sie diese redundanten Berechnungen als Teil Ihrer Komplexität betrachten oder nicht (da sie leicht weggelassen werden können).

Versuchen Version 3 in Bezug auf eine Funktion namens square Schreiben und eine Definition für square

In allen Fällen müssen Sie einige Annahmen über die Kosten der grundlegenden Operationen (*, / und +) Sie verwenden. Sie wollen wahrscheinlich sie alle Kosten O (1) zu übernehmen, aber Sie sollten das klar in Ihrer Analyse machen.