Notazione e crescita asintotica¶
Parte 3 del corso, volume 3 delle dispense. Come si confrontano le funzioni di variabile naturale che contano i passi di un algoritmo: le notazioni asintotiche Theta, O grande, Omega, o piccolo e omega, le loro proprietà e il criterio del limite; poi le famiglie di funzioni crescenti (logaritmi, potenze, esponenziali, fattoriale), la gerarchia degli infiniti e il confronto degli ordini di crescita scritto con i simboli. Limiti e funzioni di variabile naturale si danno per noti dal corso di Analisi Matematica 1.
-
9. Notazione asintotica
Notazioni \(\Theta\), \(\bigO\) e \(\Omega\) · Notazioni \(o\) e \(\omega\) · Limiti e notazioni asintotiche · Proprietà relazionali delle notazioni asintotiche · …
-
10. Crescita asintotica
Famiglie di funzioni crescenti di variabile naturale · La gerarchia degli infiniti · Confronto fra ordini di crescita