Riassunti VERIFICATO
Comportamento asintotico di una funzione
222 visualizzazioni
5 download
Nessun voto ancora
Di cosa parla
Riassunto AI · si legge in un minuto
Comportamento asintotico analizza la complessità di un algoritmo indipendentemente dal linguaggio e dalla macchina. O grande rappresenta il limite superiore, indicando che f(n) non supera cg(n). Ogni funzione polinomiale è inferiore a qualsiasi esponenziale. O piccolo indica il limite inferiore, con f(n) almeno cg(n). O stretto limita f(n) tra c1g(n) e c2g(n), inclusi i due estremi.
Leggi il riassunto completo
- Comportamento asintotico: definisce il comportamento di una funzione f(n) dopo un certo punto n0, in relazione a una funzione g(n), moltiplicata per una costante c.
- Limite asintotico superiore O(g(n)): esiste una costante c > 0 tale che f(n) ≤ cg(n) per tutti i valori di n ≥ n0. Regole: fattori costanti, somma e prodotto.
- Limite asintotico inferiore Ω(g(n)): esiste una costante c > 0 tale che f(n) ≥ cg(n) per tutti i valori di n ≥ n0.
- Limite asintotico stretto Θ(g(n)): f(n) è sia O(g(n)) che Ω(g(n)), con costanti c1 e c2 tali che c1g(n) ≤ f(n) ≤ c2g(n) per tutti i valori di n ≥ n0.
Riassunto generato con l'intelligenza artificiale a partire dagli appunti. Come lo facciamo
Stai vedendo l'anteprima delle prime pagine. Il file completo è gratis: registrati per leggerlo tutto.
Studia questi appunti con l'AI
Riassunto e domande d'esame sono gratis: chiedili e ti mandiamo un'email quando sono pronti.
In preparazione: di solito è pronto in giornata.
Questo appunto è gratis. Registrati in 30 secondi per leggere tutte le pagine e scaricarlo.
Simula l'esame con domande costruite su questi appunti.
Di cosa parla l'insegnamento
ALGORITMI E STRUTTURE DATI · 1° anno · 2° semestre · 6 CFU · ING-INF/05
L’insegnamento introduce i principi fondamentali per l’analisi, la progettazione e l’implementazione di algoritmi e strutture dati. Consolida le competenze di programmazione acquisite nell’insegnamento di Fondamenti di Programmazione e fornisce le basi metodologiche per affrontare insegnamenti successivi dell’area…