BrainTok
ENESIT

Algoritmi e strutture dati: Analisi asintotica e notazione O grande · O grande, Omega grande e Theta grande

Come O, Ω e Θ limitano la crescita di un algoritmo, e come applicarle a cicli, ricorsione e confronti reali.

Algoritmi e strutture dati · 30 domande

Prova 3 domande

1. Formalmente, che cosa significa che il tempo di esecuzione di un algoritmo è O(n²)?

  1. Per n grande, cresce al massimo come n²
  2. Per n grande, cresce almeno come n²
  3. Per ogni n, è esattamente proporzionale a n²
Mostra la risposta

Risposta: Per n grande, cresce al massimo come n²

La O grande è un limite superiore: esistono costanti c e n₀ tali che il tempo è al più c·n² per ogni n ≥ n₀.

2. Quale notazione asintotica esprime un limite inferiore alla velocità di crescita di una funzione?

  1. o piccolo (o)
  2. Omega grande (Ω)
  3. Theta grande (Θ)
Mostra la risposta

Risposta: Omega grande (Ω)

f è Ω(g) quando, per n grande, f(n) ≥ c·g(n) per qualche costante positiva c: f cresce almeno quanto g.

3. Quando una funzione è Θ(n log n)?

  1. Quando è uguale a n log n più una costante
  2. Quando n log n la limita solo dall'alto
  3. Quando n log n la limita dall'alto e dal basso
Mostra la risposta

Risposta: Quando n log n la limita dall'alto e dal basso

Θ è un limite stretto: la funzione è sia O(n log n) sia Ω(n log n), quindi sta tra due multipli costanti di n log n.

Il resto del quiz, poche domande alla volta

BrainTok ti fa qualche domanda da quiz come questi prima di aprire le app che scegli, e il tempo davanti allo schermo diventa apprendimento. Per iPhone.

Unisciti alla beta

Altri quiz di Informatica