Concetti Chiave
- La complessità misura le risorse necessarie per risolvere un problema, senza considerare valori assoluti legati a specifiche macchine o dati.
- La dimensione dei dati influisce sul consumo di risorse, mentre i casi limite analizzano i consumi migliori e peggiori di un algoritmo.
- Esistono due forme di complessità: upper bound, che analizza le risorse usate da un algoritmo, e lower bound, che determina le risorse minime necessarie per un problema.
- La notazione o-grande permette di esprimere la complessità asintotica, evidenziando come una funzione è limitata superiormente da un'altra.
- Il tempo di calcolo può variare da costante a esponenziale, con diverse strategie di ordinamento come naive e in place per gestire i dati.
Complessità = risorse necessarie a risolvere un problema (tempo di calcolo, spazio ausiliario), non interessano valori assoluti che dipendono da una specifica macchina fisica e da specifici dati
Dimensione e casi limite
Dimensione: caratteristiche dei dati dai quali dipende il consumo di risorse
Caso peggiore/migliore: configurazione che genera il peggiore/migliore consumo di risorse
Complessità in tempo/spazio: una stima della forma asintotica di come il tempo/spazio di calcolo variano in funzione della dimensione dei dati
Due forme di complessità:
- upper bound, limitazioni superiori: risorse usate da uno specifico algoritmo/programma: analisi di algoritmi/complessità concreta.
- lower bound, limitazioni inferiori: risorse necessarie per la soluzione di un problema: teoria della complessità.
- se le due analisi coincidono: un problema è classificato
Notazione o-grande
Notazione o-grande
Usata per la notazione asintotica
Notazione o-grande: date due funzioni f e g (sotto ipotesi ragionevoli su f e g) dalla dimensione dei dati in n: f è o(g) sse esistono costanti c e b e un valore della dimensione n_0 tale che per ogni n>n_0 t.c. f(n)≤c*g(n)+b
Cioè f è definitivamente maggiorata da g a meno di costanti moltiplicative e additive
Tipi di tempo di calcolo
Tempo costante
Tempo logaritmico
Tempo lineare
Tempo log-lineare
Tempo polinomiale
Tempo esponenziale
Ordinamento (sorting)
Due possibilità diverse:
- creare una copia
- ordinare in place
Algoritmi naive:
- selection sort
- insertion sort
- bubble sort
- shell sort
Domande da interrogazione
- Qual è la definizione di complessità in relazione alla risoluzione di un problema?
- Cosa si intende per caso peggiore e caso migliore nella complessità?
- Qual è la funzione della notazione o-grande nella teoria della complessità?
La complessità è definita come le risorse necessarie per risolvere un problema, che includono il tempo di calcolo e lo spazio ausiliario, senza considerare i valori assoluti legati a specifiche macchine fisiche e dati.
Il caso peggiore e il caso migliore si riferiscono alle configurazioni che generano rispettivamente il massimo e il minimo consumo di risorse durante l'esecuzione di un algoritmo, influenzando così la complessità in tempo e spazio.
La notazione o-grande è utilizzata per descrivere la notazione asintotica, indicando che una funzione f è limitata superiormente da un'altra funzione g, a meno di costanti moltiplicative e additive, per valori sufficientemente grandi della dimensione dei dati.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
