Cos'è la notazione Big-O?

Ti sei mai chiesto perché un programma che hai scritto ha impiegato così tanto tempo per essere eseguito? Forse vorresti sapere se puoi rendere il tuo codice più efficiente. Capire come viene eseguito il codice può portare il codice al livello successivo. La notazione Big-O è uno strumento utile per calcolare quanto sia efficiente il tuo codice.

Cos'è la notazione Big-O?

La notazione Big-O ti dà un modo per calcolare quanto tempo ci vorrà per eseguire il tuo codice. Puoi fisicamente calcolare il tempo di esecuzione del tuo codice, ma con questo metodo è difficile rilevare piccole differenze di orario. Ad esempio, il tempo necessario tra l'esecuzione di 20 e 50 righe di codice è molto ridotto. Tuttavia, in un programma di grandi dimensioni, queste inefficienze possono sommarsi.

La notazione Big-O conta il numero di passaggi che un algoritmo deve eseguire per misurarne l'efficienza. Avvicinarsi al codice in questo modo può essere molto efficace se è necessario ottimizzare il codice per aumentare l'efficienza. La notazione Big-O ti consentirà di misurare diversi algoritmi in base al numero di passaggi necessari per eseguire e confrontare oggettivamente l'efficienza degli algoritmi.

Come si calcola la notazione Big-O

Consideriamo due funzioni che contano quanti calzini singoli ci sono in un cassetto. Ogni funzione prende il numero di paia di calzini e restituisce il numero di calzini individuali. Il codice è scritto in Python, ma ciò non influisce sul modo in cui conteremo il numero di passaggi.

Algoritmo 1:

def sockCounter (numberOfPairs):
individualSocks = 0
per x nell'intervallo (numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

Algoritmo 2:

def sockCounter (numberOfPairs):
return numberOfPairs * 2

Questo è un esempio sciocco e dovresti essere in grado di dire facilmente quale algoritmo è più efficiente. Ma per fare pratica, esaminiamoli tutti.

RELAZIONATO: Che cos'è una funzione nella programmazione?

Che cos'è una funzione nella programmazione?

Se stai imparando a programmare il tuo codice, dovrai capire quali sono le funzioni.

L'algoritmo 1 ha molti passaggi:

1. Assegna un valore zero alla variabile individualSocks.
2. Assegna un valore di uno alla variabile i.
3. Confronta il valore di i con numberOfPairs.
4. Aggiunge due a individualSocks.
5. Assegna a se stesso il maggior valore di individualSocks.
6. Incrementa i di uno.
7. Quindi ripercorre i passaggi da 3 a 6 per lo stesso numero di volte di (indiviualSocks - 1).

Il numero di passaggi che dobbiamo completare per l'algoritmo uno può essere espresso come:

4n + 2

Ci sono quattro passaggi che dobbiamo completare n volte. In questo caso, n sarebbe uguale al valore di numberOfPairs. Ci sono anche 2 passaggi che vengono completati una volta.

In confronto, l'algoritmo 2 ha solo un passaggio. Il valore di numberOfPairs viene moltiplicato per due. Lo esprimiamo come:

1

Se non era già evidente, ora possiamo facilmente vedere che l'algoritmo 2 è più efficiente di un bel po '.

Analisi Big-O

Generalmente, quando sei interessato alla notazione Big-O di un algoritmo, sei più interessato all'efficienza complessiva e meno all'analisi a grana fine del numero di passaggi. Per semplificare la notazione, possiamo semplicemente affermare l'entità dell'efficienza.

Negli esempi precedenti, l'algoritmo 2 sarebbe espresso come uno:

O (1)

Ma l'algoritmo 1 sarebbe semplificato come:

Su)

Questa rapida istantanea ci dice come l'efficienza dell'algoritmo uno sia legata al valore di n. Maggiore è il numero, maggiore sarà il numero di passaggi che l'algoritmo dovrà completare.

Codice lineare

Poiché non conosciamo il valore di n, è più utile pensare a come il valore di n influisce sulla quantità di codice che deve essere eseguito. Nell'algoritmo 1 possiamo dire che la relazione è lineare. Se si traccia il numero di passaggi vs. il valore di n ottieni una linea retta che sale.

Codice quadratico

Non tutte le relazioni sono semplici come l'esempio lineare. Immagina di avere un array 2D e di voler cercare un valore nell'array. Potresti creare un algoritmo come questo:

def searchForValue (targetValue, arraySearched):
foundTarget = False
per x in array
per y in x:
if (y == targetValue):
foundTarget = True
return foundTarget

In questo esempio, il numero di passaggi dipende dal numero di array in arraySearched e dal numero di valori in ogni array. Quindi, il numero semplificato di passaggi sarebbe n * no n².

Questa relazione è una relazione quadratica, il che significa che il numero di passaggi nel nostro algoritmo cresce esponenzialmente con n. Nella notazione Big-O, lo scriveresti come:

O (n²)

RELAZIONATO: Strumenti utili per controllare, pulire e ottimizzare i file CSS

Codice logaritmico

Sebbene ci siano molte altre relazioni, l'ultima relazione che esamineremo sono le relazioni logaritmiche. Per rinfrescare la memoria, il log di un numero è il valore esponente richiesto per raggiungere un numero dato una base. Per esempio:

log 2 (8) = 3

Il logaritmo è uguale a tre perché se la nostra base fosse 2, avremmo bisogno di un esponente di 3 per arrivare al numero 8.

Quindi, la relazione di una funzione logaritmica è l'opposto di una relazione esponenziale. All'aumentare di n, sono necessari meno nuovi passaggi per eseguire l'algoritmo.

A prima vista, questo sembra controintuitivo. Come possono i passaggi di un algoritmo crescere più lentamente di n? Un buon esempio di ciò sono le ricerche binarie. Consideriamo un algoritmo per cercare un numero in una matrice di valori univoci.

• Inizieremo con un array per la ricerca che è in ordine dal più piccolo al più grande.
• Successivamente, controlleremo il valore al centro dell'array.
• Se il tuo numero è più alto, escluderemo i numeri più bassi dalla nostra ricerca e se il numero fosse più basso, escluderemo i numeri più alti.
• Ora, esamineremo il numero medio dei numeri rimanenti.
• Ancora una volta, escluderemo la metà dei numeri in base al fatto che il nostro valore target sia superiore o inferiore al valore medio.
• Continueremo questo processo fino a quando non troveremo il nostro obiettivo o determineremo che non è nell'elenco.

Come puoi vedere, poiché le ricerche binarie eliminano la metà dei valori possibili ad ogni passaggio, all'aumentare di n, l'effetto sul numero di volte in cui controlliamo l'array è appena influenzato. Per esprimere questo nella notazione Big-O, scriveremmo:

O (log (n))

L'importanza della notazione Big-O

Big-O nation ti offre un modo semplice e veloce per comunicare quanto sia efficiente un algoritmo. Ciò rende più facile decidere tra diversi algoritmi. Questo può essere particolarmente utile se stai usando un algoritmo da una libreria e non sai necessariamente come appare il codice.

Quando impari per la prima volta a programmare, inizi con le funzioni lineari. Come puoi vedere dal grafico sopra, questo ti porterà molto lontano. Ma man mano che diventi più esperto e inizi a creare codice più complesso, l'efficienza inizia a diventare un problema. Una comprensione di come quantificare l'efficienza del tuo codice ti fornirà gli strumenti necessari per iniziare a ottimizzarlo per l'efficienza e valutare i pro ei contro degli algoritmi.

10 errori di programmazione e codifica più comuni

Gli errori di codifica possono portare a tanti problemi. Questi suggerimenti ti aiuteranno a evitare errori di programmazione ea mantenere il tuo codice significativo.

Circa l'autore