Analizzare la complessità del codice con Python

La complessità di un algoritmo è una misura della quantità di tempo e/o spazio richiesti da un algoritmo per un input di una data dimensione (n). La complessità dell’algoritmo dipende da fattori specifici come: l’architettura del computer, cioè la piattaforma hardware, la rappresentazione del tipo di dato astratto (ADT), l’efficienza del compilatore, la complessità dell’algoritmo sottostante, la dimensione dell’input. Tuttavia, i fattori più significativi sono la complessità dell’algoritmo sottostante e la dimensione dell’input.

Nel blog di DataCamp Python Data Structures Tutorial puoi trovare una panoramica di base delle strutture dati e della loro implementazione in Python. L’articolo introduce le strutture dati fondamentali di Python. Con esso scoprirai Tipo di Dato Astratto e Struttura Dati, Strutture Dati Primitive e Non Primitive.

Analisi asintotica

L’analisi asintotica riguarda il calcolo del tempo di esecuzione di un qualsiasi frammento di codice o operazione in un’unità matematica di computazione. La sua operazione è espressa in termini di una funzione come f(n). Nell’analisi matematica, l’analisi asintotica, nota anche come asintotica, è un metodo per descrivere il comportamento al limite.

Il tempo richiesto dall’algoritmo rientra in tre tipologie: Caso pessimo - Tempo massimo richiesto da un algoritmo, ed è quello più usato quando si analizza un algoritmo. Caso migliore - Tempo minimo richiesto dall’algoritmo o dal pezzo di codice, e di norma non si calcola durante l’analisi. Caso medio - Tempo medio richiesto da un algoritmo o porzione di codice, a volte considerato nell’analisi.

Notazione asintotica

Le notazioni comunemente usate per calcolare la complessità temporale di esecuzione di un algoritmo sono le seguenti:

• Notazione Big O
• Notazione Big θ
• Notazione Big Ω

Notazione Big Oh, Ο

Big O è usata per misurare le prestazioni o la complessità di un algoritmo. In termini più matematici, è il limite superiore del tasso di crescita di una funzione, ovvero se una funzione g(x) cresce non più velocemente di una funzione f(x), allora g si dice appartenere a O(f). In generale, si usa per esprimere il limite superiore di un algoritmo e fornisce la misura per il tempo nel caso peggiore o il tempo più lungo che un algoritmo può impiegare per terminare.

Notazione Big Omega, Ω

La notazione Ω(n) è il modo formale per esprimere il limite inferiore del tempo di esecuzione di un algoritmo. Misura il tempo nel caso migliore, ovvero il minor tempo che un algoritmo può impiegare per terminare.

Notazione Big Theta, θ

La notazione θ(n) è il modo formale per esprimere sia il limite inferiore sia il limite superiore del tempo di esecuzione di un algoritmo.

La notazione viene usata per determinare la complessità di vari algoritmi

La notazione Big O è quella usata più spesso, principalmente per trovare il limite superiore di un algoritmo, mentre la notazione Big θ è talvolta usata per individuare il caso medio e la notazione Ω è la meno utilizzata tra le tre.

Vedrai esempi di notazioni usate negli algoritmi per determinarne la complessità.

Per esempio, per il quick sort:

Quick sort è un algoritmo Divide et Impera usato per l’ordinamento. Fornisce un metodo sistematico per mettere in ordine gli elementi, ad esempio disponendo i numeri in un array in ordine crescente o decrescente. Questo algoritmo sceglie un pivot, ossia un indice selezionato dall’array dato. Il pivot può essere scelto in modi diversi. Nell’esempio implementato qui sotto, il pivot è l’ultimo elemento.

Il fulcro del Quick sort è la partizione. Da un array si sceglie un elemento di partizione e poi lo si mette nella posizione corretta; quindi gli elementi maggiori della partizione vengono messi a destra del pivot, e quelli minori a sinistra.

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),

L’array ordinato è:
2
4
6
8
10
12
Otterrai l’output:

L’array ordinato è: 2 4 6 8 10 12

Ora è il momento di analizzare la complessità temporale. Per prima cosa,

• Il caso migliore è: Ω(n log(n))
• Il caso medio è: Θ(n log(n))
• Il caso peggiore è: O(n^2)

Ora analizziamo il codice sopra.

Caso migliore: è il caso in cui l’elemento di partizione sceglie come pivot l’elemento centrale. Poiché l’algoritmo verrà richiamato ricorsivamente sulla prima e sulla seconda metà, il numero totale di passi necessari è il numero di volte che occorre per passare da n a 1 dividendo il problema per 2 a ogni passo. Quindi abbiamo n/2/2/2/2/..../2=1 per k volte. Nota però che l’equazione corretta è: n / 2^k = 1. Poiché 2^logn = n, otteniamo k = logn. Dunque il numero di passi (iterazioni) richiesti dall’algoritmo è O(log n), il che rende l’algoritmo O(n log n), dato che ogni iterazione costa O(n).

Caso medio: per il caso medio bisogna considerare tutte le permutazioni dell’array e calcolare il tempo impiegato da ciascuna. Puoi approfondire qui: Merge sort.

Caso peggiore: nel caso peggiore, se il primo elemento è scelto come pivot, la complessità nel caso peggiore si verifica quando l’input da ordinare è in ordine crescente o decrescente. Il motivo è che, dopo la partizione, una parte avrà dimensione 1 e l’altra dimensione n-1. Qui, T(n) è la funzione: quindi, il tempo per fare quick sort su ‘n’ elementi T(n) = Tempo per partizionare ‘n’ elementi O(n) + Tempo per fare quick sort su ‘n-1’ elementi T(n-1). Quindi T(n) = T(n-1) + O(n) => T(n) = O(n^2)

Esempi

Il codice seguente non sarà particolarmente raffinato, e potresti non considerarlo un algoritmo, ma puoi farlo perché qualsiasi codice che fa qualcosa è tecnicamente un algoritmo, ossia un modo per risolvere un problema specifico. L’algoritmo che vedi sopra usa un ciclo for contenente una singola istruzione di stampa.

print('I love Python');

Ciao mondo!
La complessità temporale dell’algoritmo sopra è O(1) perché richiede sempre un solo passo. È tempo costante.

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs Come descriveresti l’efficienza dell’algoritmo sopra in notazione Big O?

Per analizzare l’algoritmo sopra, devi considerare quante operazioni compie. Nel caso mostrato, ci sono quattro elementi in una lista e devi stamparne ognuno una volta. Ma ora pensa: se ci fossero più di 4 elementi nella lista, ad esempio 15, il ciclo for impiegherebbe lo stesso numero di passi anche con 15 elementi? Poiché questo ciclo for esegue tanti passi quanti sono gli elementi, si dice che l’algoritmo ha efficienza O(N) piuttosto che O(1).

Il prossimo esempio è un semplice algoritmo in Python per determinare se un numero è primo:

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False

Il codice precedente accetta un numero come argomento e avvia un ciclo for in cui dividi ogni numero da 2 fino a quel numero per vedere se c’è un resto. Se non c’è resto, sai che il numero non è primo e restituisci immediatamente False. Se arrivi fino al numero trovando sempre un resto, allora sai che il numero è primo e restituisci True.

Puoi determinare che l’efficienza dell’algoritmo sopra è O(N). Nell’esempio non si ricevono dati sotto forma di array o lista, ma il numero passato come argomento. Se passi un numero arbitrario come 11, il ciclo for esegue circa undici passi. (In realtà ne esegue nove, dato che parte da due e termina subito prima del numero stesso.) Per il numero 101, il ciclo esegue circa 101 passi. Poiché il numero di passi aumenta di pari passo con il numero passato alla funzione, questo è un classico esempio di O(N).

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);

Nel codice sopra, la complessità dell’algoritmo è O(N). Poiché il secondo ciclo ha 100 come argomento, lo si può ignorare perché si esprime la complessità assumendo N molto grande.

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);

Ci sono due cicli: la lunghezza di uno è m e quella dell’altro è n. Assumendo m e n grandi, la complessità dell’operazione è O(n+m). Poiché i cicli sono separati e prendono input diversi, la complessità è additiva.

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));

C’è un ciclo for annidato e, assumendo n e m grandi, la complessità dell’operazione è O(n*m). Poiché i cicli sono gli stessi e annidati, la complessità è moltiplicativa.

Complimenti!

Sei arrivato alla fine di questo tutorial! Lungo il percorso, hai imparato la notazione asintotica, uno strumento di base usato da programmatori e data scientist. Hai appena appreso un modo semplice per analizzare la complessità, scritto in inglese semplice, senza tecnicismi e rigore matematico. Anche se strutture dati e algoritmi sono spesso studiati solo se sei uno studente di informatica o in un campo correlato, è ugualmente importante avere conoscenze di base su questo argomento, senza dover essere esperti. Per approfondire, puoi fare riferimento a questo link: MIT opencourseware Algorithm course

Se vuoi imparare di più su Python, dai un’occhiata a questi corsi DataCamp: