complessità misurazione per alimentare un numero

Question

I implementato un programma per alimentare un numero (a ^ n) mediante la tecnica divide et impera. Ho implementato due versioni dello stesso problema:

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

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

Versione 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: Quale una delle versioni di cui sopra hanno una complessità di θ(lg n)?

Q2: Se la versione 2 ha la complessità di θ(lg n), perché? Perché anche se la dimensione del problema nella versione 2 è stato diviso per due, il numero di problemi secondari sono anche due, così mi sento versione 2 crescerà nell'ordine di θ(nlg n).

Non sono sicuro circa la mia conclusione.

Grazie

Answer 1

Nella versione 1, non c'è nessuna risposta, come si usa una funzione chiamata pow che mai definire, quindi non si può davvero dire ciò che la complessità è.

Nella versione 2, non ci sono calcoli ridondanti, quindi la risposta dipende dal fatto che si considera questi calcoli ridondanti come parte della vostra complessità o meno (in quanto possono facilmente essere lasciato fuori).

Provare a scrivere la versione 3 in termini di una funzione chiamata square e inserire una definizione di square

In tutti i casi è necessario un qualche ipotesi circa il costo delle operazioni di base (*, /, e +) si usa. Probabilmente si desidera assumere tutti O costo (1), ma si dovrebbe fare questa precisazione nella vostra analisi.