La versione più recente è stata modificata il 2006-03-02 18:22:40 da ViViana
Aggiunzioni:
~~L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^{n-1} mosse).
Omissioni:
~~L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^n-1 mosse).
Modificato il 2006-03-02 18:21:41 da ViViana
Aggiunzioni:
~ 2) Complessità sottolineare: O(n ), con k<1
Omissioni:
~ 2) Complessità sottolineare: O(n ), con k<1 k
Modificato il 2006-03-02 18:20:47 da ViViana
Aggiunzioni:
| ALGORTIMO |
CASO MIGLIORE |
CASO MEDIO |
CASO PEGGIORE |
| Ordinamento Ingenuo |
O(n^2) |
O(n^2) |
O(n^2) |
| Selection Sort |
O(n) |
|
O(n^2) |
| Bubble Sort |
O(n) |
|
O(n^2) |
| Counting Sort |
O(n) |
O(n) |
O(n) |
| Quick Sort |
O(n log n) |
O(n log n) |
O(n^2) |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
Un algoritmo si dice efficiente se il suo tempo di esecuzione è limitato superiormente da una funzione polinomiale (funzione limitata superiormente da n^k per un opportuno fissato intero k).
Omissioni:
| ALGORTIMO |
CASO MIGLIORE |
CASO MEDIO |
CASO PEGGIORE |
| Ordinamento Ingenuo |
O(n_2) |
O(n_2) |
O(n_2) |
| Selection Sort |
O(n) |
|
O(n^2) |
| Bubble Sort |
O(n) |
|
O(n_2) |
| Counting Sort |
O(n) |
O(n) |
O(n) |
| Quick Sort |
O(n log n) |
O(n log n) |
O(n_2) |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
Un algoritmo si dice efficiente se il suo tempo di esecuzione è limitato superiormente da una funzione polinomiale (funzione limitata superiormente da n^ k per un opportuno fissato intero k).
Modificato il 2006-03-02 18:19:43 da ViViana
Aggiunzioni:
~ 5) Complessità quadratica n^ k , con k>=2: O(n^k )
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^n-1 mosse).
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^(n-1) mosse).
Modificato il 2006-03-02 18:18:32 da ViViana
Aggiunzioni:
| ALGORTIMO |
CASO MIGLIORE |
CASO MEDIO |
CASO PEGGIORE |
| Ordinamento Ingenuo |
O(n_2) |
O(n_2) |
O(n_2) |
| Selection Sort |
O(n) |
|
O(n^2) |
| Bubble Sort |
O(n) |
|
O(n_2) |
| Counting Sort |
O(n) |
O(n) |
O(n) |
| Quick Sort |
O(n log n) |
O(n log n) |
O(n_2) |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
L'algoritmo della Torre di Hanoi ha complessità O(
2^n) (sono necessarie
2^(n-1) mosse).
Omissioni:
| ALGORTIMO |
CASO MIGLIORE |
CASO MEDIO |
CASO PEGGIORE |
| Ordinamento Ingenuo |
O(n_2) |
O(n_2) |
O(n_2) |
| Selection Sort |
O(n) |
|
O( |
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^(n-1) mosse).
Modificato il 2006-03-02 18:17:32 da ViViana
Aggiunzioni:
| ALGORTIMO |
CASO MIGLIORE |
CASO MEDIO |
CASO PEGGIORE |
| Ordinamento Ingenuo |
O(n_2) |
O(n_2) |
O(n_2) |
| Selection Sort |
O(n) |
|
O( |
È posseduta dagli algoritmi che eseguono un numero di operazioni sostanzialmente proporzionale ad n.
Es.: ricerca sequenziale, somma di numeri di n cifre, merge di due file, ecc.
5) Complessità
quadratica n^k , con k>=2: O(
n^k)
Es.: Bubblesort ( O(n^2) ), moltiplicazione di due 2 matrici ( O(n^3) ), ecc.
Es.: un algoritmo che debba produrre tutte le possibili stringhe lunghe n di k simboli avrà complessità O(k^n) cioè esponenziale.
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^(n-1) mosse).
Un algoritmo si dice efficiente se il suo tempo di esecuzione è limitato superiormente da una funzione polinomiale (funzione limitata superiormente da n^k per un opportuno fissato intero k).
Omissioni:
| ALGORTIMO |
CASO MIGLIORE |
CASO MEDIO |
CASO PEGGIORE |
| Ordinamento Ingenuo |
O(n_2) |
O(n_2) |
O(n_2) |
| Selection Sort |
O(n) |
|
O(n_2) |
| Bubble Sort |
O(n) |
|
O(n_2) |
| Counting Sort |
O(n) |
O(n) |
O(n) |
| Quick Sort |
O(n log n) |
O(n log n) |
O(n_2) |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
È posseduta dagli algoritmi che eseguono un numero di operazioni sostanzialmente proporzionale ad n. Es.: ricerca sequenziale, somma di numeri di n cifre, merge di due file, ecc.
5) Complessità
quadratica n^k , con k>=2: O(n^k)
Es.: Bubblesort ( O(n^2) ), moltiplicazione di due 2 matrici ( O(n^3) ), ecc.
Es.: un algoritmo che debba produrre tutte le possibili stringhe lunghe n di k simboli avrà complessità O(k^n) cioè esponenziale.
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^n - 1 mosse).
Un algoritmo si dice efficiente se il suo tempo di esecuzione è limitato superiormente da una funzione polinomiale (funzione limitata superiormente da n^k per un opportuno fissato intero k).
Modificato il 2006-03-02 18:13:40 da ViViana
Aggiunzioni:
Un problema è computazionalmente trattabile se esiste un algoritmo efficiente che lo risolve; altrimenti il problema è computazionalmente intrattabile.
Un algoritmo si dice efficiente se il suo tempo di esecuzione è limitato superiormente da una funzione polinomiale (funzione limitata superiormente da n^k per un opportuno fissato intero k).
Modificato il 2006-03-02 18:12:46 da ViViana
Aggiunzioni:
~~Tutte le classi di complessità elencate precedentemente vengono genericamente considerate come polinomiali. Esse sono caratterizzate dal fatto che la dimensione n non compare mai come esponente in alcun modo. Quando ciò avviene si parla invece di complessità esponenziale.
Es.: un algoritmo che debba produrre tutte le possibili stringhe lunghe n di k simboli avrà complessità O(k^n) cioè esponenziale.
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^n - 1 mosse).
È necessario guardare con particolare diffidenza agli algoritmi dotati di complessità esponenziale, perché possono richiedere dei tempi di esecuzione proibitivi (se non addirittura astronomici) anche per valori relativamente piccoli di n ed indipendentemente dalla velocità dell'elaboratore.
Purtroppo esistono molti problemi, anche di interesse pratico, per i quali non si conoscono ancora algoritmi non esponenziali (problemi intrattabili). Es.: problema del commesso viaggiatore.
Omissioni:
Tutte le classi di complessità elencate precedentemente vengono genericamente considerate come polinomiali. Esse sono caratterizzate dal fatto che la dimensione n non compare mai come esponente in alcun modo. Quando ciò avviene si parla invece di complessità esponenziale.
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^n - 1 mosse).
È necessario guardare con particolare diffidenza agli algoritmi dotati di complessità esponenziale, perché possono richiedere dei tempi di esecuzione proibitivi (se non addirittura astronomici) anche per valori relativamente piccoli di n ed indipendentemente dalla velocità dell'elaboratore.
Purtroppo esistono molti problemi, anche di interesse pratico, per i quali non si conoscono ancora algoritmi non esponenziali (problemi intrattabili). Es.: problema del commesso viaggiatore.
Modificato il 2006-03-02 18:11:50 da ViViana
Aggiunzioni:
~~È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
Es.:Ricerca binaria, o logaritmica, ecc.
È posseduta dagli algoritmi che eseguono un numero di operazioni sostanzialmente proporzionale ad n. Es.: ricerca sequenziale, somma di numeri di n cifre, merge di due file, ecc.
E’ la più ottimale complessità che gli algoritmi di ordinamento possono raggiungere.
Es.: Bubblesort ( O(n^2) ), moltiplicazione di due 2 matrici ( O(n^3) ), ecc.
Omissioni:
È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
Es.:Ricerca binaria, o logaritmica, ecc.
È posseduta dagli algoritmi che eseguono un numero di operazioni sostanzialmente proporzionale ad n. Es.: ricerca sequenziale, somma di numeri di n cifre, merge di due file, ecc.
E’ la più ottimale complessità che gli algoritmi di ordinamento possono raggiungere.
Es.: Bubblesort ( O(n^2) ), moltiplicazione di due 2 matrici ( O(n^3) ), ecc.
Modificato il 2006-03-02 18:11:21 da ViViana
Aggiunzioni:
È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
Omissioni:
~~È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
Modificato il 2006-03-02 18:11:05 da ViViana
Aggiunzioni:
~~È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
Omissioni:
~~ È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
Modificato il 2006-03-02 18:10:52 da ViViana
Aggiunzioni:
~~ È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
Omissioni:
~ È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Modificato il 2006-03-02 18:10:33 da ViViana
Aggiunzioni:
~ È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
Es.:Ricerca binaria, o logaritmica, ecc.
È posseduta dagli algoritmi che eseguono un numero di operazioni sostanzialmente proporzionale ad n. Es.: ricerca sequenziale, somma di numeri di n cifre, merge di due file, ecc.
E’ la più ottimale complessità che gli algoritmi di ordinamento possono raggiungere.
Es.: Bubblesort ( O(n^2) ), moltiplicazione di due 2 matrici ( O(n^3) ), ecc.
Omissioni:
È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.:Ricerca binaria, o logaritmica, ecc.
È posseduta dagli algoritmi che eseguono un numero di operazioni sostanzialmente proporzionale ad n. Es.: ricerca sequenziale, somma di numeri di n cifre, merge di due file, ecc.
E’ la più ottimale complessità che gli algoritmi di ordinamento possono raggiungere.
Es.: Bubblesort ( O(n^2) ), moltiplicazione di due 2 matrici ( O(n^3) ), ecc.
Modificato il 2006-03-02 18:10:02 da ViViana
Aggiunzioni:
~ 4) Complessità n log n: O(n log n)
5) Complessità
quadratica n^k , con k>=2: O(n^k)
6) Complessità
fattoriale
7) Complessità
esponenziale
Omissioni:
4) Complessità n log n: O(n log n)
Complessità quadratica n^k , con k>=2: O(n^k)
Complessità fattoriale
Complessità esponenziale
Modificato il 2006-03-02 18:09:42 da ViViana
Aggiunzioni:
~ 1) Complessità costante: O(1)
2) Complessità sottolineare: O(n ), con k<1 k
3) Complessità lineare: O(n)
Omissioni:
~1) Complessità costante: O(1)
Complessità sottolineare: O(n ), con k<1 k
Complessità lineare: O(n)
Modificato il 2006-03-02 18:05:47 da ViViana
Aggiunzioni:
~1) Complessità costante: O(1)
Omissioni:
~1) elenco numerato:
Modificato il 2006-03-02 18:03:11 da ViViana
Aggiunzioni:
~1) elenco numerato:
1) Complessità costante: O(1)
Omissioni:
~1) Complessità costante: O(1)
Modificato il 2006-03-02 18:01:34 da ViViana
Aggiunzioni:
~1) Complessità costante: O(1)
- Complessità sottolineare: O(n ), con k<1 k
- Complessità lineare: O(n)
- Complessità n log n: O(n log n)
- Complessità quadratica n^k , con k>=2: O(n^k)
- Complessità fattoriale
- Complessità esponenziale
Omissioni:
1) Complessità costante: O(1)
Complessità sottolineare: O(n ), con k<1 k
Complessità lineare: O(n)
Complessità n log n: O(n log n)
Complessità quadratica n^k , con k>=2: O(n^k)
Complessità fattoriale
Complessità esponenziale
Modificato il 2006-03-02 17:59:47 da ViViana
Aggiunzioni:
CLASSI DI COMPLESSITA’
Complessità costante: O(1)
È posseduta dagli algoritmi che eseguono sempre lo stesso numero di operazioni indipendentemente dalla dimensione dei dati.
Es.: inserimento o estrazione dalla testa di una lista concatenata, ecc.
- Complessità sottolineare: O(n ), con k<1 k
Es.:Ricerca binaria, o logaritmica, ecc.
- Complessità lineare: O(n)
È posseduta dagli algoritmi che eseguono un numero di operazioni sostanzialmente proporzionale ad n. Es.: ricerca sequenziale, somma di numeri di n cifre, merge di due file, ecc.
- Complessità n log n: O(n log n)
E’ la più ottimale complessità che gli algoritmi di ordinamento possono raggiungere.
- Complessità quadratica n^k , con k>=2: O(n^k)
Es.: Bubblesort ( O(n^2) ), moltiplicazione di due 2 matrici ( O(n^3) ), ecc.
- Complessità fattoriale
- Complessità esponenziale
Tutte le classi di complessità elencate precedentemente vengono genericamente considerate come polinomiali. Esse sono caratterizzate dal fatto che la dimensione n non compare mai come esponente in alcun modo. Quando ciò avviene si parla invece di complessità esponenziale.
Es.: un algoritmo che debba produrre tutte le possibili stringhe lunghe n di k simboli avrà complessità O(k^n) cioè esponenziale.
L'algoritmo della Torre di Hanoi ha complessità O(2^n) (sono necessarie 2^n - 1 mosse).
È necessario guardare con particolare diffidenza agli algoritmi dotati di complessità esponenziale, perché possono richiedere dei tempi di esecuzione proibitivi (se non addirittura astronomici) anche per valori relativamente piccoli di n ed indipendentemente dalla velocità dell'elaboratore.
Purtroppo esistono molti problemi, anche di interesse pratico, per i quali non si conoscono ancora algoritmi non esponenziali (problemi intrattabili). Es.: problema del commesso viaggiatore.
La versione più vecchia di questa pagina è stata modificata il 2006-03-02 17:58:20 da ViViana []
Vista della pagina:
COMPLESSITA' DEGLI ALGORITMI
Il
\mathit{“costo”} dell'esecuzione di un algoritmo dipende non solo dalla dimensione dei dati in Input, ma anche da quanto è “disordinato” il vettore da ordinare. Infatti, se il vettore è già ordinato (o quasi), terminano in breve tempo, mentre se è "molto disordinato" devono eseguire molti più passi.
Si distinguono tre casi: caso peggiore, caso medio e caso migliore.
La ricerca e l'ottimizzazione di algoritmi di ordinamento è molto importante in ambito informatico e per queste classi di algoritmi sono stati dimostrati svariati teoremi che ne definiscono i limiti. Il più importante è il seguente:
Teorema del LOWER BOUND: La complessità in tempo di un qualsiasi algoritmo di ordinamento basato su confronti è di almeno
\Omega(n log n) [cioè deve effettuare almeno (n log n) confronti], dove n è il numero di elementi da ordinare.
| ALGORTIMO |
CASO MIGLIORE |
CASO MEDIO |
CASO PEGGIORE |
| Ordinamento Ingenuo |
O(n_2) |
O(n_2) |
O(n_2) |
| Selection Sort |
O(n) |
|
O(n_2) |
| Bubble Sort |
O(n) |
|
O(n_2) |
| Counting Sort |
O(n) |
O(n) |
O(n) |
| Quick Sort |
O(n log n) |
O(n log n) |
O(n_2) |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
Torna a Programmazione e Lab.
