Che cos'è la notazione O grande? Come vieni con figure come O (n)?

Question

Eventuali duplicati:
Plain english explanation of Big O

Mi piacerebbe immaginare questo è probabilmente qualcosa insegnato nelle classi, ma come ho un programmatore autodidatta, ho visto solo raramente.

Ho capito che ha qualcosa a che fare con il tempo, e O (1) è il migliore, mentre roba come O (n^n) è molto brutto, ma qualcuno potrebbe indicarmi una spiegazione di base di cosa in realtà rappresenta e da dove vengono questi numeri?

Answer 1

Big O si riferisce all'ordine di esecuzione del caso peggiore. Viene utilizzato per mostrare quanto bene un algoritmo scala in base alla dimensione del set di dati (n-> numero di elementi).

Poiché ci occupiamo solo dell'ordine, i moltiplicatori costanti vengono ignorati e vengono rimossi anche i termini che aumentano meno rapidamente del termine dominante. Alcuni esempi:

Una singola operazione o una serie di operazioni è O (1), poiché richiede un tempo costante (non varia in base alla dimensione del set di dati).

Un ciclo è O (n). Ogni elemento nel set di dati viene ripetuto.

Un ciclo nidificato è O (n^2). Un ciclo annidato annidato è O (n^3) e in avanti.

Le cose come la ricerca dell'albero binario sono log (n), che è più difficile da mostrare, ma a ogni livello dell'albero, il numero possibile di soluzioni è dimezzato, quindi il numero di livelli è log (n) (fornito l'albero è equilibrato).

Qualcosa come trovare la somma di un insieme di numeri che è più vicino ad un dato valore è O (n!), Poiché la somma di ogni sottoinsieme deve essere calcolata. Questo è molto cattivo.

Answer 2

È un modo di esprimere la complessità del tempo.

O(n) significa per gli elementi n in un elenco, ci vogliono i calcoli n per ordinare l'elenco. Che non è affatto male. Ogni aumento di n aumenta la complessità del tempo in modo lineare.

O(n^n) non è corretto, poiché la quantità di calcolo richiesta per eseguire un ordinamento (o qualsiasi altra cosa si stia facendo) aumenterà in modo esponenziale man mano che si aumenta n.

O(1) è il migliore, poiché significa 1 calcolo per eseguire una funzione, pensare alle tabelle hash, cercare un valore in una tabella hash ha O(1) complessità temporale.

Answer 3

La notazione O grande applicata a un algoritmo si riferisce al modo in cui il tempo di esecuzione dell'algoritmo dipende dalla quantità di dati di input. Ad esempio, un algoritmo di ordinamento richiederà più tempo per ordinare un set di dati di grandi dimensioni rispetto a un set di dati di piccole dimensioni. Se per l'esempio di algoritmo di ordinamento si calcola il tempo di esecuzione (asse verticale) rispetto al numero di valori da ordinare (asse orizzontale), per il numero di valori da zero a un numero grande, la natura della linea o della curva che ne risulta dipende dall'algoritmo di ordinamento utilizzato. La notazione Big O è un metodo abbreviato per descrivere la linea o la curva.

Nella notazione O grande, l'espressione tra parentesi è la funzione rappresentata graficamente.Se una variabile (ad esempio n) è inclusa nell'espressione, questa variabile fa riferimento alla dimensione del set di dati di input. Tu dici che O (1) è il migliore. Questo è vero perché il grafico f (n) = 1 non varia con n. Un algoritmo O (1) richiede la stessa quantità di tempo per completare indipendentemente dalla dimensione del set di dati di input. Al contrario, il tempo di esecuzione di un algoritmo di O (n^n) aumenta con il quadrato della dimensione dell'insieme di dati di input.

Questa è l'idea di base, per una spiegazione dettagliata, consultare la pagina di wikipedia intitolata "Big O Notation".