Scheda: Complessità temporale Big O

Che cosa rappresenta Big O?

Big O è una notazione utilizzata per descrivere la complessità temporale di un algoritmo, rappresentando il suo comportamento al crescere dell'input.

Definisci la complessità temporale.

La complessità temporale è una misura di quanto tempo impiega un algoritmo per completare la sua esecuzione in funzione della dimensione dell'input.

Vero o falso: Big O misura solo il tempo di esecuzione.

Falso: Big O misura sia il tempo di esecuzione che la memoria utilizzata da un algoritmo.

Completa la frase: Big O è limitato da...

...un valore superiore che rappresenta il tempo massimo di esecuzione in relazione alla dimensione dell'input.

Qual è il significato di O(1)?

O(1) indica una complessità costante, dove il tempo di esecuzione non cambia al variare della dimensione dell'input.

Confronta O(n) e O(n^2).

O(n) è lineare e cresce proporzionalmente all'input; O(n^2) è quadratica e cresce con il quadrato dell'input.

Che cosa significa O(log n)?

O(log n) rappresenta una complessità logaritmica, comune in algoritmi di ricerca binaria, dove il tempo di esecuzione cresce lentamente con l'aumento dell'input.

Causa → Effetto: Aumentare l'input in O(n^3).

Aumentare l'input porta a un aumento cubico del tempo di esecuzione dell'algoritmo.

Definisci il termine 'asintotico'.

Asintotico si riferisce al comportamento di un algoritmo quando la dimensione dell'input tende all'infinito, utile per analizzare la complessità con Big O.

Qual è l'importanza di Big O negli algoritmi?

Big O aiuta a confrontare l'efficienza di diversi algoritmi e a scegliere il migliore in base alla complessità temporale.

Vero o falso: O(n) è sempre migliore di O(n^2).

Vero: O(n) è più efficiente poiché il tempo di esecuzione cresce meno rapidamente rispetto a O(n^2).

Qual è la relazione tra complessità e ottimizzazione?

Una minore complessità temporale significa algoritmi più veloci e migliori prestazioni, facilitando l'ottimizzazione del codice.

Che cosa indica O(n log n)?

O(n log n) è una complessità comune in algoritmi di ordinamento efficienti, come il mergesort, dove il tempo di esecuzione è più rapido di O(n^2).

Quali sono i limiti della notazione Big O?

Big O non considera fattori costanti e non fornisce informazioni su casi migliori o peggiori, solo sul comportamento asintotico.

Esempio pratico: O(n) con un loop.

In un ciclo che scorre un array di dimensione n, il tempo di esecuzione è O(n), poiché esegue n operazioni.

O(1) vs O(n): quale è più veloce?

O(1) è più veloce di O(n) poiché il tempo di esecuzione rimane costante indipendentemente dalla dimensione dell'input.

Complessità costante

La complessità costante è $\displaystyle O(1)$. Significa che il tempo di esecuzione non varia con l'aumento dell'input.

Complessità logaritmica

La complessità logaritmica è $\displaystyle O( ext{log} n)$. Tipicamente si verifica in algoritmi di ricerca binaria.

Comp. lineare vs comp. quadratica

Comp. lineare: $\displaystyle O(n)$, comp. quadratica: $\displaystyle O(n^2)$. La quadratica cresce molto più rapidamente con n.

Esempio di complessità cubica

Un algoritmo di ordinamento come il 'bubble sort' ha una complessità cubica di $\displaystyle O(n^3)$ in scenari particolari.

Qual è la complessità di ricerca lineare?

La ricerca lineare ha complessità $\displaystyle O(n)$. Controlla ogni elemento uno per uno.

Complessità logaritmica è sempre migliore?

Vero. Gli algoritmi logaritmici sono più efficienti rispetto a quelli lineari per quantità elevate di dati.

Esempio di complessità costante

Accesso a un elemento in un array ha complessità $\displaystyle O(1)$, perché non dipende dalle dimensioni dell'array.

Quando si verifica la complessità quadratica?

La complessità quadratica $\displaystyle O(n^2)$ si verifica in algoritmi che confrontano tutti gli elementi tra loro.

Complessità lineare

La complessità lineare è $\displaystyle O(n)$. Rappresenta algoritmi che operano in proporzione all'input.

Vero o falso: $\displaystyle O(n^2)$ è più veloce di $\displaystyle O(n)$?

Falso. $\displaystyle O(n)$ è più veloce di $\displaystyle O(n^2)$ per grandi valori di n.

Cosa indica $\displaystyle O(1)$?

$\displaystyle O(1)$ indica che il tempo di esecuzione rimane costante, indipendentemente dalla grandezza dell'input.

Comp. cubica è più lenta di...

Comp. quadratica. $\displaystyle O(n^3)$ cresce più rapidamente rispetto a $\displaystyle O(n^2)$ con l'aumento di n.

Ricerca binaria

Ha complessità $\displaystyle O( ext{log } n)$, utile per cercare in liste ordinate.

Ordinamento per inserimento

Ha complessità $\displaystyle O(n^2)$ nel caso peggiore. Adatto per piccole liste.

Vero o Falso: $\displaystyle O(n) > O( ext{log } n)$

Vero. La crescita lineare è sempre maggiore rispetto a quella logaritmica.

Esempio di complessità costante.

Accesso a un elemento in un array: $\displaystyle O(1)$. Sempre lo stesso tempo.

Confronta ricerca lineare e ricerca binaria.

Ricerca lineare: $\displaystyle O(n)$ Ricerca binaria: $\displaystyle O( ext{log } n)$ La binaria è più veloce.

Esempio di algoritmo quadratico.

Ordinamento per bolle ha complessità $\displaystyle O(n^2)$. Inefficiente per grandi liste.

Scrivi la complessità dell'algoritmo di Merge Sort.

Merge Sort ha complessità $\displaystyle O(n ext{ log } n)$. Efficiente per ordinare.

Vero o Falso: $\displaystyle O(n^2)$ è migliore di $\displaystyle O(n)$

Falso. $\displaystyle O(n)$ è sempre migliore, cresce più lentamente.

Esempio di complessità logaritmica.

Trovare un elemento in una lista ordinata: $\displaystyle O( ext{log } n)$.

Cosa determina la complessità di un algoritmo?

La quantità di operazioni in relazione alla dimensione dei dati.

Esempio di algoritmo cubico.

Calcolo di tutte le combinazioni in un array: $\displaystyle O(n^3)$, inefficiente.

Effetto di aumentare n su $\displaystyle O(n^2)$

Incrementa il tempo di esecuzione quadraticamente, rallenta significativamente.