O-grande

Big O Notation è un modo per confrontare gli algoritmi. Li confronta calcolando quanta memoria è necessaria e quanto tempo ci vuole per completarli.

La Big O Notation è spesso utilizzata per identificare la complessità di un problema, nota anche come classe di complessità del problema. Il matematico Paul Bachmann (1837-1920) fu il primo ad utilizzare questa notazione, nella seconda edizione del suo libro "Analytische Zahlentheorie", nel 1896. Edmund Landau (1877-1938) rese popolare la notazione. Per questo motivo, quando si parla di un simbolo Landau, ci si riferisce a questa notazione.

Big O Notation prende il nome dal termine "ordine della funzione", che si riferisce alla crescita delle funzioni. La Big O Notation è usata per trovare il limite superiore (la quantità più alta possibile) del tasso di crescita della funzione, il che significa che funziona il più lungo tempo necessario per trasformare l'ingresso in uscita. Ciò significa che un algoritmo può essere raggruppato in base a quanto tempo può richiedere in uno scenario peggiore, in cui il percorso più lungo sarà effettuato ogni volta.

Big O è un'espressione che trova il tempo di esecuzione nel peggiore dei casi, mostrando quanto sia efficiente un algoritmo senza dover eseguire il programma su un computer. Questo è utile anche perché computer diversi possono avere hardware diverso e quindi hanno bisogno di tempi diversi per completarlo.

Esempi

I seguenti esempi utilizzano tutti codice scritto in Python. Si noti che questa non è una lista completa dei tipi Big O.

Costante

O ( 1 ) O(1)} $O(1)$ . Richiede sempre la stessa quantità di tempo indipendentemente dall'input. Per esempio, prendere una funzione che accetta un numero intero (chiamato x) e restituisce il doppio del suo valore:

def doppio(x): ritorno x * 2 # Restituire il valore di x volte 2

Dopo aver accettato l'ingresso, questa funzione esegue sempre un passo per restituire un'uscita. E' costante perché ci vorrà sempre lo stesso tempo, quindi è O ( 1 ) {\i} $O(1)$ .

Lineare

O ( n ) O(n)} $O(n)$ . Aumenta in base alla dimensione dell'input, rappresentato da n {\a6} . Supponiamo che una funzione accetti n, e restituisca ogni numero da 1 a n:

def count(n): i = 1 #Crea un contatore chiamato "i" con un valore di 1 mentre i <= n: #Mentre i è minore o uguale a n print(i) #Stampa il valore di i i i = i + 1 #Ridefinisci i come "il valore di i + 1".

Se dovessimo inserire il valore di 5 allora questo emetterebbe 1 , 2 , 3 , 3 , 4 , 4 , 5 {\i} $1,2,3,4,5$ che richiede 5 cicli da completare. Allo stesso modo, se ne immettiamo 100 uscirebbe 1 , 2 , 3...98 , 99 , 100 {\i} $1,2,3...98,99,100$ , che richiede 100 loop per essere completato. Se l'ingresso è n {\i} allora il tempo di esecuzione dell'algoritmo è esattamente n {\i}displaystyle n} loop ogni volta, quindi è O ( n ) {\i}displaystyle O(n)} $O(n)$ .

Fattoriale

O ( n ! ) O ( n ! ) O(n!) $O(n!)$ . Aumenta in quantità fattoriale, il che significa che il tempo impiegato aumenta enormemente con l'input. Per esempio, diciamo di voler visitare cinque città in tutto il mondo e di voler vedere ogni possibile ordine (permutazione). Un algoritmo che potremmo scrivere usando la libreria itertools di Python è il seguente:

importare itertools #Importare le città della biblioteca itertools = ['Londra', 'Parigi', 'Berlino', 'Amsterdam', 'Roma'] #Una serie delle nostre città scelte def permutazioni: #Importare un array di città come input: per i in itertools. permutazioni: #Per ogni permutazione dei nostri elementi (assegnati alla variabile "i") print(i) #Output i

Questo algoritmo calcolerà ogni permutazione unica delle nostre città e poi la produrrà. Esempi di output includeranno:

("Londra", "Parigi", "Berlino", "Amsterdam", "Roma") ("Londra", "Parigi", "Berlino", "Roma", "Amsterdam") ("Londra", "Parigi", "Amsterdam", "Berlino", "Roma") ... ("Roma", "Amsterdam", "Parigi", "Berlino", "Londra") ("Roma", "Amsterdam", "Berlino", "Londra", "Parigi") ("Roma", "Amsterdam", "Berlino", "Parigi", "Londra")

Qui la nostra lista di input è lunga 5 voci, e per ogni selezione le nostre opzioni rimanenti diminuiscono di 1. In altre parole i nostri 5 input scelgono 5 × 4 × 3 × 2 × 1 {\i}displaystyle 5 \times 4 \times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ items (o 5 ! {\i}displaystyle 5!} $5!$ ). Se il nostro ingresso è n {\displaystyle n} città lungo, allora il numero di uscite è n ! In $n!$ altre parole, supponendo di passare attraverso ogni permutazione che richiediamo i $O(n!)$ loop O ( n ! ) O(n!) per completarla.

Little-o Notazione

Una versione più severa della Grande O è la Little O. La differenza tra la grande O grande e la piccola-o è che la piccola-o è un rigoroso limite superiore: mentre la O ( n ) {\i} $O(n)$ significa che il tempo di completamento aumenterà fino a questo massimo in base alla dimensione dell'ingresso, la o ( n ) {\i} $o(n)$ significa che il tempo di completamento sarà generalmente al di sotto di questa quantità di tempo. In altre parole, Big O presuppone che ogni ciclo prenderà il percorso più lungo e il processo durerà il più a lungo possibile, mentre little-o è più realistico sui tempi di esecuzione effettivi; se il numero di cicli è basato sul lancio di un dado a 6 facce Big O supporrà sempre che venga lanciato un 6, mentre little-o terrà conto dell'uguale probabilità che vengano lanciati altri numeri.

Domande e risposte

D: Cos'è la notazione Big O?

R: La notazione Big O è un modo per confrontare i tassi di crescita di diverse funzioni, spesso utilizzata per confrontare l'efficienza di diversi algoritmi, calcolando la quantità di memoria e il tempo necessario per completarli. Può anche essere utilizzata per identificare la complessità di un problema.

D: Chi è stato il primo a utilizzare questa notazione?

R: Il matematico Paul Bachmann (1837-1920) è stato il primo ad utilizzare questa notazione nel suo libro "Analytische Zahlentheorie" nel 1896.

D: Per cosa sta la Grande O?

R: Big O sta per "ordine della funzione", che si riferisce al tasso di crescita delle funzioni.

D: Come si usa la Big O?

R: La notazione Big O viene utilizzata per trovare un limite superiore (l'importo più alto possibile) sul tasso di crescita della funzione, il che significa che calcola il tempo più lungo necessario per trasformare un input in un output. Ciò significa che gli algoritmi possono essere raggruppati in base al tempo che impiegano negli scenari peggiori, dove il percorso più lungo verrà seguito ogni volta.

D: Cosa sono i simboli di Landau?

R: I simboli Landau si riferiscono alla notazione Big O, che prende il nome da Edmund Landau (1877-1938) che ha reso popolare questa notazione.

D: Perché la Big O è utile?

R:Big O ci permette di misurare la velocità senza dover eseguire i programmi sui computer, poiché assume sempre gli scenari peggiori, rendendoli coerenti indipendentemente dalle differenze hardware tra i computer. Inoltre, mostra l'efficienza di un algoritmo senza doverlo eseguire su un computer.