Notazione Big O e analisi degli algoritmi con esempi di Python

Introduzione

Di solito ci sono diversi modi per risolvere il problema utilizzando un programma per computer. Ad esempio, ci sono diversi modi per ordinare gli elementi in un array: puoi usare unisci ordinamento, Bubble sort, ordinamento per inserzione, e così via. Tutti questi algoritmi hanno i loro pro e contro e il compito dello sviluppatore è valutarli per poter scegliere l'algoritmo migliore da utilizzare in ogni caso d'uso. In altre parole, la domanda principale è quale algoritmo utilizzare per risolvere un problema specifico quando esistono più soluzioni al problema.

Analisi algoritmica si riferisce all'analisi della complessità di diversi algoritmi e alla ricerca dell'algoritmo più efficiente per risolvere il problema in questione. Notazione Big-O è una misura statistica usata per descrivere la complessità dell'algoritmo.

In questa guida, faremo prima una breve rassegna dell'analisi dell'algoritmo e poi daremo uno sguardo più approfondito alla notazione Big-O. Vedremo come la notazione Big-O può essere utilizzata per trovare la complessità dell'algoritmo con l'aiuto di diverse funzioni Python.

Perché l'analisi degli algoritmi è importante?

Per capire perché l'analisi dell'algoritmo è importante, prenderemo l'aiuto di un semplice esempio. Supponiamo che un manager dia il compito a due dei suoi dipendenti di progettare un algoritmo in Python che calcoli il fattoriale di un numero inserito dall'utente. L'algoritmo sviluppato dal primo dipendente si presenta così:

def fact(n):
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print(fact(5))

Si noti che l'algoritmo prende semplicemente un numero intero come argomento. Dentro il fact() funzione una variabile denominata product è inizializzato a 1. Un ciclo viene eseguito da 1 a n e durante ogni iterazione, il valore in product viene moltiplicato per il numero che viene ripetuto dal ciclo e il risultato viene memorizzato in product di nuovo variabile. Dopo l'esecuzione del ciclo, il product variabile conterrà il fattoriale.

Allo stesso modo, anche il secondo impiegato ha sviluppato un algoritmo che calcola il fattoriale di un numero. Il secondo impiegato ha utilizzato una funzione ricorsiva per calcolare il fattoriale del numero n:

def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print(fact2(5))

Il manager deve decidere quale algoritmo utilizzare. Per fare ciò, hanno deciso di scegliere quale algoritmo funziona più velocemente. Un modo per farlo è trovare il tempo necessario per eseguire il codice sullo stesso input.

Nel taccuino Jupyter, puoi usare il file %timeit letterale seguito dalla chiamata alla funzione per trovare il tempo impiegato dalla funzione per l'esecuzione:

%timeit fact(50)

Questo ci darà:

9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

L'output dice che l'algoritmo prende 9 microsecondi (più/meno 45 nanosecondi) per ciclo.

Allo stesso modo, possiamo calcolare quanto tempo impiega il secondo approccio per eseguire:

%timeit fact2(50)

Ciò comporterà:

15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Il secondo algoritmo che coinvolge la ricorsione prende 15 microsecondi (più/meno 427 nanosecondi).

Il tempo di esecuzione mostra che il primo algoritmo è più veloce rispetto al secondo algoritmo che coinvolge la ricorsione. Quando si ha a che fare con input di grandi dimensioni, la differenza di prestazioni può diventare più significativa.

Tuttavia, il tempo di esecuzione non è una buona metrica per misurare la complessità di un algoritmo poiché dipende dall'hardware. È necessaria una metrica di analisi della complessità più obiettiva per un algoritmo. Questo è dove il Notazione O grande viene a giocare.

Analisi algoritmica con notazione Big-O

La notazione Big-O indica la relazione tra l'input dell'algoritmo e i passaggi necessari per eseguire l'algoritmo. È indicato da una grande "O" seguita da una parentesi di apertura e chiusura. All'interno di parentesi, la relazione tra l'input e i passi effettuati dall'algoritmo è presentata utilizzando “n”.

Il punto chiave è: Big-O non è interessato a a particolare istanza in cui si esegue un algoritmo, ad esempio fact(50), ma piuttosto, quanto bene lo fa scala dato un input crescente. Questa è una metrica molto migliore per la valutazione rispetto al tempo concreto per un'istanza concreta!

Ad esempio, se esiste un relazione lineare tra l'input e il passo compiuto dall'algoritmo per completare la sua esecuzione, sarà utilizzata la notazione Big-O O (n). Allo stesso modo, la notazione Big-O per funzioni quadratiche is O(n²).

Per costruire l'intuizione:

• O (n): a n=1, viene eseguito 1 passaggio. In n=10, vengono eseguiti 10 passaggi.
• O(n²): a n=1, viene eseguito 1 passaggio. In n=10, vengono eseguiti 100 passaggi.

At n=1, questi due si esibiranno allo stesso modo! Questo è un altro motivo per cui osservare la relazione tra l'input e il numero di passaggi per elaborare quell'input è meglio che valutare semplicemente le funzioni con un input concreto.

Di seguito sono elencate alcune delle funzioni Big-O più comuni:

Nome	grande oh
costante	O (c)
Lineare	O (n)
quadratico	O(n²)
Cubic	O(n³)
Esponenziale	O(2ⁿ)
Logaritmico	O (log (n))
Log lineare	O(nlog(n))

Puoi visualizzare queste funzioni e confrontarle:

In generale, qualsiasi cosa peggio di lineare è considerata una cattiva complessità (cioè inefficiente) e dovrebbe essere evitata se possibile. La complessità lineare va bene e di solito è un male necessario. Logaritmico è buono. Costante è incredibile!

Per avere un'idea di come viene calcolato un Big-O, diamo un'occhiata ad alcuni esempi di complessità costante, lineare e quadratica.

Complessità costante – O(C)

La complessità di un algoritmo si dice costante se i passaggi necessari per completare l'esecuzione di un algoritmo rimangono costanti, indipendentemente dal numero di input. La complessità costante è indicata da O (c) where c può essere qualsiasi numero costante.

Scriviamo un semplice algoritmo in Python che trovi il quadrato del primo elemento della lista e poi lo stampi a schermo:

def constant_algo(items):
    result = items[0] * items[0]
    print(result)

constant_algo([4, 5, 6, 8])

Nello script sopra, indipendentemente dalla dimensione dell'inputo il numero di elementi nell'elenco di input items, l'algoritmo esegue solo 2 passaggi:

1. Trovare il quadrato del primo elemento
2. Stampa del risultato sullo schermo.

Quindi, la complessità rimane costante.

Se si disegna un grafico a linee con le dimensioni variabili di items immesso sull'asse X e il numero di passi sull'asse Y, otterrai una linea retta. Creiamo un breve script per aiutarci a visualizzarlo. Indipendentemente dal numero di ingressi, il numero di passaggi eseguiti rimane lo stesso:

steps = []
def constant(n):
    return 1
    
for i in range(1, 100):
    steps.append(constant(i))
plt.plot(steps)

Complessità lineare – O (n)

La complessità di un algoritmo si dice lineare se i passaggi necessari per completare l'esecuzione di un algoritmo aumentano o diminuiscono linearmente con il numero di input. La complessità lineare è indicata da O (n).

In questo esempio, scriviamo un semplice programma che visualizzi tutti gli elementi nell'elenco sulla console:

def linear_algo(items):
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

La complessità del linear_algo() la funzione è lineare nell'esempio precedente poiché il numero di iterazioni del ciclo for sarà uguale alla dimensione dell'input items schieramento. Ad esempio, se ci sono 4 elementi nel file items list, il ciclo for verrà eseguito 4 volte.

Creiamo rapidamente un grafico per l'algoritmo di complessità lineare con il numero di input sull'asse x e il numero di passaggi sull'asse y:

steps = []
def linear(n):
    return n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

Ciò comporterà:

Una cosa importante da notare è che con input di grandi dimensioni, le costanti tendono a perdere valore. Questo è il motivo per cui in genere rimuoviamo le costanti dalla notazione Big-O e un'espressione come O(2n) viene solitamente abbreviata in O(n). Sia O(2n) che O(n) sono lineari: ciò che conta è la relazione lineare, non il valore concreto. Ad esempio, modifichiamo il linear_algo():

def linear_algo(items):
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

Ci sono due cicli for che ripetono l'input items elenco. Quindi la complessità dell'algoritmo diventa O (2n), tuttavia nel caso di elementi infiniti nell'elenco di input, il doppio dell'infinito è ancora uguale all'infinito. Possiamo ignorare la costante 2 (poiché in definitiva è insignificante) e la complessità dell'algoritmo rimane O (n).

Visualizziamo questo nuovo algoritmo tracciando gli input sull'asse X e il numero di passi sull'asse Y:

steps = []
def linear(n):
    return 2*n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

Nello script sopra, puoi vederlo chiaramente y=2n, tuttavia, l'output è lineare e si presenta così:

Complessità quadratica – O(n²)

Si dice che la complessità di un algoritmo è quadratica quando i passaggi necessari per eseguire un algoritmo sono una funzione quadratica del numero di elementi nell'input. La complessità quadratica è indicata come O(n²):

def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ' ,item2)

quadratic_algo([4, 5, 6, 8])

Abbiamo un ciclo esterno che scorre tutti gli elementi nell'elenco di input e quindi un ciclo interno nidificato, che itera di nuovo tutti gli elementi nell'elenco di input. Il numero totale di passaggi eseguiti è n*n, dove n è il numero di elementi nell'array di input.

Il grafico seguente traccia il numero di input rispetto ai passaggi per un algoritmo con complessità quadratica:

Complessità logaritmica – O (log)

Alcuni algoritmi raggiungono la complessità logaritmica, come Ricerca binaria. Ricerca binaria cerca un elemento in un array, selezionando il mezzo di un array e sfoltire la metà in cui l'elemento non lo è. Lo fa di nuovo per la metà rimanente e continua gli stessi passaggi fino a trovare l'elemento. In ogni passaggio, esso metà il numero di elementi nell'array.

Ciò richiede l'ordinamento dell'array e l'assunzione di un'ipotesi sui dati (ad esempio, l'ordinamento).

Quando puoi fare ipotesi sui dati in entrata, puoi adottare misure che riducono la complessità di un algoritmo. La complessità logaritmica è auspicabile, poiché consente di ottenere buone prestazioni anche con input altamente scalati.

Trovare la complessità delle funzioni complesse?

Negli esempi precedenti, avevamo funzioni abbastanza semplici sull'input. Tuttavia, come calcoliamo il Big-O delle funzioni che chiamano (più) altre funzioni sull'input?

Diamo un'occhiata:

def complex_algo(items):

    for i in range(5):
        print("Python is awesome")

    for item in items:
        print(item)

    for item in items:
        print(item)

    print("Big O")
    print("Big O")
    print("Big O")

complex_algo([4, 5, 6, 8])

Nello script sopra vengono eseguite diverse attività, in primo luogo, una stringa viene stampata 5 volte sulla console utilizzando print dichiarazione. Successivamente, stampiamo l'elenco di input due volte sullo schermo e, infine, un'altra stringa viene stampata tre volte sulla console. Per trovare la complessità di un tale algoritmo, dobbiamo scomporre il codice dell'algoritmo in parti e cercare di trovare la complessità dei singoli pezzi. Segna la complessità di ogni pezzo.

Nella prima sezione abbiamo:

for i in range(5):
	print("Python is awesome")

La complessità di questa parte è O (5) poiché in questo pezzo di codice vengono eseguiti cinque passaggi costanti indipendentemente dall'input.

Successivamente, abbiamo:

for item in items:
	print(item)

Sappiamo che la complessità del pezzo di codice sopra è O (n). Allo stesso modo, anche la complessità del seguente pezzo di codice è O (n):

for item in items:
	print(item)

Infine, nel seguente pezzo di codice, una stringa viene stampata tre volte, quindi la complessità lo è O (3):

print("Big O")
print("Big O")
print("Big O")

Per trovare la complessità complessiva, dobbiamo semplicemente aggiungere queste singole complessità:

O(5) + O(n) + O(n) + O(3)

Semplificando quanto sopra otteniamo:

O(8) + O(2n) = O(8+2n)

Abbiamo detto in precedenza che quando l'input (che in questo caso ha lunghezza n) diventa estremamente grande, le costanti diventano insignificanti, cioè il doppio o la metà dell'infinito rimane ancora infinito. Pertanto, possiamo ignorare le costanti. La complessità finale dell'algoritmo sarà O (n)!

Complessità peggiore e migliore

Di solito, quando qualcuno ti chiede della complessità di un algoritmo, è interessato alla complessità del caso peggiore (Big-O). A volte, potrebbero essere interessati anche alla complessità del caso migliore (Big-Omega).

Per capire la relazione tra questi, diamo un'occhiata a un altro pezzo di codice:

def search_algo(num, items):
    for item in items:
        if item == num:
            return True
        else:
            pass
nums = [2, 4, 6, 8, 10]

print(search_algo(2, nums))

Nello script sopra, abbiamo una funzione che accetta un numero e un elenco di numeri come input. Restituisce vero se il numero passato si trova nell'elenco dei numeri, altrimenti restituisce None. Se cerchi 2 nell'elenco, verrà trovato nel primo confronto. Questa è la complessità del caso migliore dell'algoritmo in quanto l'elemento cercato si trova nel primo indice cercato. La migliore complessità del caso, in questo caso, è O (1). D'altra parte, se cerchi 10, verrà trovato nell'ultimo indice cercato. L'algoritmo dovrà cercare tra tutti gli elementi nell'elenco, quindi la complessità del caso peggiore diventa O (n).

Oltre alla complessità del caso migliore e peggiore, puoi anche calcolare la complessità media (Big-Theta) di un algoritmo, che ti dice "dato un input casuale, qual è la complessità temporale prevista dell'algoritmo"?

Complessità spaziale

Oltre alla complessità temporale, dove conteggi il numero di passaggi necessari per completare l'esecuzione di un algoritmo, puoi trovare anche il complessità spaziale che si riferisce alla quantità di spazio che è necessario allocare in memoria durante l'esecuzione di un programma.

Dai un'occhiata al seguente esempio:

def return_squares(n):
    square_list = []
    for num in n:
        square_list.append(num * num)

    return square_list

nums = [2, 4, 6, 8, 10]
print(return_squares(nums))

I return_squares() La funzione accetta un elenco di numeri interi e restituisce un elenco con i quadrati corrispondenti. L'algoritmo deve allocare memoria per lo stesso numero di elementi dell'elenco di input. Pertanto, la complessità spaziale dell'algoritmo diventa O (n).

Conclusione

La notazione Big-O è la metrica standard utilizzata per misurare la complessità di un algoritmo. In questa guida, abbiamo studiato cos'è la notazione Big-O e come può essere utilizzata per misurare la complessità di una varietà di algoritmi. Abbiamo anche studiato diversi tipi di funzioni Big-O con l'aiuto di diversi esempi di Python. Infine, abbiamo brevemente esaminato la complessità del caso peggiore e del caso migliore insieme alla complessità spaziale.