Notazione O grande è un potente strumento utilizzato in informatica per descrivere la complessità temporale o spaziale degli algoritmi. Fornisce un modo standardizzato per confrontare l'efficienza di diversi algoritmi in termini di prestazioni nel caso peggiore. Comprensione Notazione O grande è essenziale per analizzare e progettare algoritmi efficienti.
In questo tutorial tratteremo le basi di Notazione O grande , il suo significato e come analizzare la complessità degli algoritmi che utilizzano Grande O .
Tabella dei contenuti
- Cos'è la notazione Big-O?
- Definizione della notazione Big-O:
- Perché la notazione O grande è importante?
- Proprietà della notazione Big O
- Notazioni comuni per la O grande
- Come determinare la notazione Big O?
- Esempi matematici di analisi runtime
- Esempi algoritmici di analisi runtime
- Classi di algoritmi con numero di operazioni e tempo di esecuzione
- Confronto tra la notazione Big O, la notazione Big Ω (Omega) e la notazione Big θ (Theta)
- Domande frequenti sulla notazione O grande
Cos'è la notazione Big-O?
Big-O , comunemente indicato come Ordine di , è un modo per esprimere il limite superiore della complessità temporale di un algoritmo, poiché analizza il nel caso peggiore situazione dell'algoritmo. Fornisce un limite superiore sul tempo impiegato da un algoritmo in termini di dimensione dell'input. È indicato come O(f(n)) , Dove f(n) è una funzione che rappresenta il numero di operazioni (passi) che un algoritmo esegue per risolvere un problema di dimensione N .
100 kmh in mph
Notazione O-grande è usato per descrivere le prestazioni o la complessità di un algoritmo. Nello specifico, descrive il nella peggiore delle ipotesi in termini di tempo O complessità spaziale.
Punto importante:
- Notazione O grande descrive solo il comportamento asintotico di una funzione, non il suo valore esatto.
- IL Notazione O grande può essere utilizzato per confrontare l'efficienza di diversi algoritmi o strutture dati.
Definizione della notazione Big-O:
Date due funzioni f(n) E g(n) , lo diciamo f(n) È O(g(n)) se esistono costanti c> 0 E N 0 >= 0 tale che f(n) <= c*g(n) per tutti n>= n 0 .
In termini più semplici, f(n) È O(g(n)) Se f(n) non cresce più velocemente di c*g(n) per tutti n>= n0dove c e n0sono costanti.
Perché la notazione O grande è importante?
La notazione Big O è una notazione matematica utilizzata per descrivere la complessità temporale o l'efficienza nel caso peggiore di un algoritmo o la complessità spaziale nel caso peggiore di una struttura dati. Fornisce un modo per confrontare le prestazioni di diversi algoritmi e strutture dati e per prevedere come si comporteranno all'aumentare della dimensione dell'input.
La notazione Big O è importante per diversi motivi:
- La notazione Big O è importante perché aiuta ad analizzare l'efficienza degli algoritmi.
- Fornisce un modo per descrivere come tempo di esecuzione O requisiti di spazio di un algoritmo crescono all’aumentare della dimensione dell’input.
- Consente ai programmatori di confrontare diversi algoritmi e scegliere quello più efficiente per un problema specifico.
- Aiuta a comprendere la scalabilità degli algoritmi e a prevedere come si comporteranno all'aumentare della dimensione dell'input.
- Consente agli sviluppatori di ottimizzare il codice e migliorare le prestazioni generali.
Proprietà della notazione Big O:
Di seguito sono riportate alcune importanti proprietà della notazione Big O:
1. Riflessività:
Per ogni funzione f(n), f(n) = O(f(n)).
Esempio:
f(n) = n2, allora f(n) = O(n2).
2. Transitività:
Se f(n) = O(g(n)) e g(n) = O(h(n)), allora f(n) = O(h(n)).
Esempio:
f(n) = n3, g(n) = n2, h(n) = n4. Allora f(n) = O(g(n)) e g(n) = O(h(n)). Pertanto, f(n) = O(h(n)).
3. Fattore costante:
Per ogni costante c> 0 e funzioni f(n) e g(n), se f(n) = O(g(n)), allora cf(n) = O(g(n)).
Esempio:
f(n) = n, g(n) = n2. Allora f(n) = O(g(n)). Pertanto, 2f(n) = O(g(n)).
4. Regola della somma:
Se f(n) = O(g(n)) e h(n) = O(g(n)), allora f(n) + h(n) = O(g(n)).
Esempio:
f(n) = n2, g(n) = n3, h(n) = n4. Allora f(n) = O(g(n)) e h(n) = O(g(n)). Pertanto, f(n) + h(n) = O(g(n)).
5. Regola del prodotto:
Se f(n) = O(g(n)) e h(n) = O(k(n)), allora f(n) * h(n) = O(g(n) * k(n)) .
Esempio:
f(n) = n, g(n) = n2, h(n) = n3, k(n) = n4. Allora f(n) = O(g(n)) e h(n) = O(k(n)). Pertanto, f(n) * h(n) = O(g(n) * k(n)) = O(n5).
6. Regola di composizione:
Se f(n) = O(g(n)) e g(n) = O(h(n)), allora f(g(n)) = O(h(n)).
Esempio:
f(n) = n2, g(n) = n, h(n) = n3. Allora f(n) = O(g(n)) e g(n) = O(h(n)). Pertanto, f(g(n)) = O(h(n)) = O(n3).
Java lancia la stringa su int
Notazioni comuni per la O grande:
La notazione Big-O è un modo per misurare la complessità temporale e spaziale di un algoritmo. Descrive il limite superiore della complessità nello scenario peggiore. Esaminiamo i diversi tipi di complessità temporale:
1. Complessità temporale lineare: grande complessità O(n).
La complessità temporale lineare significa che il tempo di esecuzione di un algoritmo cresce linearmente con la dimensione dell'input.
Ad esempio, considera un algoritmo that attraversa un array per trovare un elemento specifico :
Snippet di codice bool findElement(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return true; } } return false; }> 2. Complessità temporale logaritmica: complessità Big O(log n).
La complessità temporale logaritmica significa che il tempo di esecuzione di un algoritmo è proporzionale al logaritmo della dimensione dell'input.
Ad esempio, a algoritmo di ricerca binaria ha una complessità temporale logaritmica:
Snippet di codice int binarySearch(int arr[], int l, int r, int x) { if (r>= l) { int medio = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid]> x) return BinarySearch(arr, l, mid - 1, x); return ricercabinaria(arr, mid + 1, r, x); } ritorna -1; }> 3. Complessità temporale quadratica: Big O(n2) Complessità
La complessità temporale quadratica significa che il tempo di esecuzione di un algoritmo è proporzionale al quadrato della dimensione dell'input.
Ad esempio, un semplice algoritmo di ordinamento delle bolle ha una complessità temporale quadratica:
Snippet di codice void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { scambia(&arr[j], &arr[j + 1]); } } } }> 4. Complessità temporale cubica: Big O(n3) Complessità
La complessità temporale cubica significa che il tempo di esecuzione di un algoritmo è proporzionale al cubo della dimensione dell'input.
Ad esempio, un ingenuo algoritmo di moltiplicazione di matrici ha una complessità temporale cubica:
Snippet di codice void multiply(int mat1[][N], int mat2[][N], int res[][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { res[i][j] = 0; for (int k = 0; k < N; k++) res[i][j] += mat1[i][k] * mat2[k][j]; } } }> 5. Complessità temporale polinomiale: Big O(nK) Complessità
La complessità temporale polinomiale si riferisce alla complessità temporale di un algoritmo che può essere espressa come una funzione polinomiale della dimensione dell'input N . In Grande O notazione, si dice che un algoritmo abbia complessità temporale polinomiale se la sua complessità temporale lo è SU K ) , Dove K è una costante e rappresenta il grado del polinomio.
Gli algoritmi con complessità temporale polinomiale sono generalmente considerati efficienti, poiché il tempo di esecuzione cresce a un ritmo ragionevole all'aumentare della dimensione dell'input. Esempi comuni di algoritmi con complessità temporale polinomiale includono complessità temporale lineare O(n) , complessità temporale quadratica O(n 2 ) , E complessità temporale cubica O(n 3 ) .
6. Complessità temporale esponenziale: Big O(2N) Complessità
La complessità temporale esponenziale significa che il tempo di esecuzione di un algoritmo raddoppia con ogni aggiunta al set di dati di input.
Ad esempio, il problema di generare tutti i sottoinsiemi di un insieme ha complessità temporale esponenziale:
Snippet di codice void generateSubsets(int arr[], int n) { for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if (i & (1 << j)) { cout << arr[j] << ' '; } } cout << endl; } }> Complessità temporale fattoriale: grande complessità O(n!)
La complessità temporale fattoriale significa che il tempo di esecuzione di un algoritmo cresce fattorialmente con la dimensione dell'input. Questo è spesso visto negli algoritmi che generano tutte le permutazioni di un insieme di dati.
Ecco un esempio di un algoritmo di complessità temporale fattoriale, che genera tutte le permutazioni di un array:
Snippet di codice void permute(int* a, int l, int r) { if (l == r) { for (int i = 0; i <= r; i++) { cout << a[i] << ' '; } cout << endl; } else { for (int i = l; i <= r; i++) { swap(a[l], a[i]); permute(a, l + 1, r); swap(a[l], a[i]); // backtrack } } }> Se tracciassimo gli esempi più comuni di notazione Big O, avremmo un grafico come questo:
Come determinare la notazione Big O?
Notazione O grande è una notazione matematica usata per descrivere il comportamento asintotico di una funzione man mano che il suo input diventa infinitamente grande. Fornisce un modo per caratterizzare l'efficienza degli algoritmi e delle strutture dati.
carattere Java in stringa
Passaggi per determinare la notazione O grande:
1. Identificare il termine dominante:
- Esaminare la funzione e identificare il termine con l'ordine di crescita più elevato all'aumentare della dimensione dell'input.
- Ignora eventuali fattori costanti o termini di ordine inferiore.
2. Determinare l'ordine di crescita:
- L'ordine di crescita del termine dominante determina la notazione Big O.
3. Scrivi la notazione Big O:
- La notazione Big O è scritta come O(f(n)), dove f(n) rappresenta il termine dominante.
- Ad esempio, se il termine dominante è n^2, la notazione Big O sarà O(n^2).
4. Semplifica la notazione (facoltativo):
- In alcuni casi, il Marchio Big O n può essere semplificato rimuovendo i fattori costanti o utilizzando una notazione più concisa.
- Ad esempio, O(2n) può essere semplificato in SU).
Esempio:
Funzione: f(n) = 3n3+ 2n2+5n+1
- Termine dominante: 3n3
- Ordine di crescita: cubico (n3)
- Notazione O grande: O(n3)
- Notazione semplificata: O(n3)
Esempi matematici di analisi runtime:
La tabella seguente illustra l'analisi di runtime di diversi ordini di algoritmi all'aumentare della dimensione dell'input (n).
| N | registro(n) | N | n * log(n) | n^2 | 2^n | N! |
|---|---|---|---|---|---|---|
| 10 | 1 | 10 | 10 | 100 | 1024 | 3628800 |
| venti | 2.996 | venti | 59,9 | 400 | 1048576 | 2.432902e+1818 |
Esempi algoritmici di analisi runtime:
La tabella seguente classifica gli algoritmi in base alla loro complessità di runtime e fornisce esempi per ciascun tipo.
| Tipo | Notazione | Algoritmi di esempio |
|---|---|---|
| Logaritmico | O(log n) | Ricerca binaria |
| Lineare | SU) | Ricerca lineare |
| Superlineare | O(n log n) | Ordinamento heap, ordinamento unione |
| Polinomio | O(n^c) | Moltiplicazione di matrici di Strassen, Bubble Sort, Selection Sort, Insertion Sort, Bucket Sort |
| Esponenziale | O(c^n) | Torre di Hanoi |
| Fattoriale | SU!) | Espansione determinante per minori, algoritmo di ricerca della forza bruta per il problema del commesso viaggiatore |
Classi di algoritmi con numero di operazioni e tempo di esecuzione:
Di seguito sono riportate le classi di algoritmi e i relativi tempi di esecuzione su un computer in esecuzione 1 milione di operazioni al secondo (1 sec = 10 6 μsec = 10 3 ms) :
Classi di notazione O grande | f(n) | Analisi Big O (numero di operazioni) per n = 10 | Tempo di esecuzione (1 istruzione/μsec) |
|---|---|---|---|
costante | O(1) | 1 | 1 microsecondo |
logaritmico | O(log) sottostringa in Java | 3.32 | 3 μsec |
lineare | SU) | 10 | 10 μsec |
O(logn) | O(logn) | 33.2 | 33 μsec |
quadratico | SU2) | 102 | 100 microsecondi |
cubo | SU3) | 103 | 1 ms |
esponenziale | O(2N) | 1024 | 10 millisecondi |
fattoriale | SU!) | 10! | 3,6288 secondi |
Confronto tra la notazione Big O, la notazione Big Ω (Omega) e la notazione Big θ (Theta):
Di seguito è riportata una tabella che confronta la notazione Big O, la notazione Ω (Omega) e la notazione θ (Theta):
| Notazione | Definizione | Spiegazione |
|---|---|---|
| Grande O (O) | f(n) ≤ C * g(n) per ogni n ≥ n0 | Descrive il limite superiore del tempo di esecuzione dell'algoritmo nel file caso peggiore . |
| Ω (Omega) | f(n) ≥ C * g(n) per ogni n ≥ n0 | Descrive il limite inferiore del tempo di esecuzione dell'algoritmo nel file caso migliore . |
| θ (Theta) | C1* g(n) ≤ f(n) ≤ C2* g(n) per n ≥ n0 | Descrive sia il limite superiore che quello inferiore dell'algoritmo tempo di esecuzione . |
In ogni notazione:
- f(n) rappresenta la funzione analizzata, tipicamente la complessità temporale dell'algoritmo.
- g(n) rappresenta una funzione specifica che delimita f(n) .
- C, C1, E C2 sono costanti.
- N 0 è la dimensione minima dell'input oltre la quale vale la disuguaglianza.
Queste notazioni vengono utilizzate per analizzare algoritmi basati sulla loro caso peggiore (Big O) , caso migliore (Ω) , E caso medio (θ) scenari.
Domande frequenti sulla notazione O grande:
Domanda 1. Cos'è la notazione Big O?
Risposta: La Big O Notation è una notazione matematica utilizzata per descrivere il limite superiore della complessità temporale di un algoritmo in termini di come cresce rispetto alla dimensione dell’input.
Domanda 2. Perché la notazione O grande è importante?
Risposta: Ci aiuta ad analizzare e confrontare l'efficienza degli algoritmi concentrandoci sullo scenario peggiore e comprendendo come le loro prestazioni si adattano alle dimensioni dell'input.
Domanda 3. Come viene calcolata la notazione Big O?
Risposta: La notazione Big O viene determinata identificando l'operazione dominante in un algoritmo ed esprimendo la sua complessità temporale in termini di n, dove n rappresenta la dimensione dell'input.
stringa di formato java
Domanda 4. Cosa significa O(1) nella notazione Big O?
Risposta: O(1) indica complessità temporale costante, indicando che il tempo di esecuzione di un algoritmo non cambia indipendentemente dalla dimensione dell’input.
Domanda 5. Qual è il significato delle diverse complessità Big O come O(log n) o O(n^2)?
Risposta: Diverse complessità come O(log n) o O(n^2) rappresentano il modo in cui le prestazioni di un algoritmo scalano all'aumentare della dimensione dell'input, fornendo informazioni sulla sua efficienza e scalabilità.
Domanda 6. La notazione Big O può essere applicata anche alla complessità dello spazio?
Risposta: Sì, la Big O Notation può essere utilizzata anche per analizzare e descrivere la complessità spaziale di un algoritmo, indicando quanta memoria richiede in relazione alla dimensione dell’input.
Articolo correlato:
- Esempi di analisi Big-O
- Progettazione e analisi di algoritmi
- Tipi di notazioni asintotiche nell'analisi della complessità degli algoritmi
- Analisi degli algoritmi | Notazione Big – Ω (Big-Omega).
- Analisi degli algoritmi | piccola o e piccola notazione omega