Efficienza: tempo di esecuzione e complessità spaziale

Concetti di Informatica

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Introduzione alla notazione Big-O

  • Misura crescita di tempo e spazio al crescere dell'input
  • Esempi: $O(n)$, $O(n^2)$, $O(\log n)$
  • "O" indica l’ordine di crescita, es. O(n) = lineare
Concetti di Informatica

Complessità temporale - analogia d’ufficio

Un grafico che mostra le varie complessità Big O

  • $O(1)$ - tempo costante - "Sguardo rapido" - "costante"
  • $O(\log n)$ - aumento lento del tempo - "Divisione a metà" - "logaritmica"
  • $O(n)$ - aumento lineare - "Lettura documento" - "lineare"
  • $O(n\,\log n)$ - aumento più rapido - "Ordinare una pila" - "linearitmica"
  • $O(n^2)$ - aumento quadratico - "Confronto documenti" - "quadratica"
Concetti di Informatica

Complessità spaziale - analogia d’ufficio

Un grafico che mostra le varie complessità Big O

  • $O(1)$ - spazio costante - "Spazio sulla scrivania" - "costante"
  • $O(\log n)$ - aumento lento dello spazio - "note minime" - "logaritmica"
  • $O(n)$ - aumento lineare - "post-it" - "lineare"
  • $O(n\,\log n)$ - aumento più rapido dello spazio - "pile temporanee" - "linearitmica"
  • $O(n^2)$ - aumento quadratico dello spazio - "griglia di confronto" - "quadratica"
Concetti di Informatica

Ayo berlatih!

Concetti di Informatica

Preparing Video For Download...