04: Tempo di Calcolo e Complessità Asintotica

Il numero di operazioni elementari eseguite da un algoritmo per un dato input. Questa misura è proporzionale al tempo di esecuzione e indipendente dal tipo di computer e linguaggio di programmazione.

Il tempo di calcolo nel caso migliore corrisponde al numero minimo di operazioni eseguite per tutti gli input di una data dimensione.

Il tempo di calcolo nel caso peggiore corrisponde al numero massimo di operazioni eseguite per tutti gli input di una data dimensione.

Studia il comportamento di un algoritmo quando la dimensione degli input cresce all'infinito, ignorando le costanti e concentrandosi sul termine dominante.

Una funzione che descrive la complessità asintotica di un algoritmo, indica come il tempo di calcolo cresce al crescere della dimensione dell'input.

Il numero di operazioni per un algoritmo in relazione alla dimensione dell'input. Si può calcolare per il caso migliore, caso peggiore o caso medio.

Il tempo di esecuzione medio di un algoritmo per tutti gli input di una data dimensione.

Il numero di operazioni eseguite da un algoritmo dipende dall'input stesso.

La dimensione massima di un problema che può essere risolto in un determinato lasso di tempo su un dato computer.

La notazione Big O viene utilizzata per descrivere la crescita di una funzione, trascurando le costanti moltiplicative e un numero finito di valori.

Una funzione f(n) è O di g(n) se esiste una costante c > 0 e un intero n0 tali che per ogni n > n0, f(n) ≤ cg(n). In parole povere, f(n) cresce al massimo come g(n), a meno di una costante moltiplicativa e un numero finito di valori.

L'aumento della velocità del computer ha un impatto limitato sulla dimensione massima di un problema che può essere risolto. La dimensione massima cresce solo in modo logaritmico rispetto alla velocità. Questo dimostra che la velocità del computer non è l'unico fattore limitante per la grandezza dei problemi risolvibili.

T(n) = an + b è O(n). Ciò significa che la funzione cresce linearmente con n.

T(n) = a2n2 + a1n + a0 è O(n2). Questo indica che la funzione cresce quadraticamente con n.

Le costanti non vengono considerate nella notazione Big O perché l'obiettivo è studiare il comportamento asintotico delle funzioni, quindi le costanti non influenzano la crescita.

Le stime esatte delle costanti sono molto difficili da ottenere nella pratica, quindi è più importante analizzare la crescita asintotica delle funzioni piuttosto che preoccuparsi delle costanti.

Un'espressione matematica che indica il limite superiore della velocità di crescita di una funzione, ovvero il valore massimo che la funzione può raggiungere per grandi valori di n.

Un'espressione matematica che indica il limite inferiore della velocità di crescita di una funzione, ovvero il valore minimo che la funzione può raggiungere per grandi valori di n.

Un'espressione matematica che indica il limite superiore e inferiore della velocità di crescita di una funzione., ovvero il valore massimo che la funzione può raggiungere per grandi valori di n.

Una funzione f(n) è O(g(n)) se esiste una costante c maggiore di 0 e un valore n0 tale che per ogni n maggiore di n0, la funzione f(n) è minore o uguale a c * g(n). In pratica, la funzione g(n) fornisce un limite superiore per f(n) per grandi valori di n.

Una funzione f(n) è Θ(g(n)) se esistono due costanti c1 e c2 maggiori di 0 e un valore n0 tale che per ogni n maggiore di n0, la funzione f(n) è compresa tra c1 * g(n) e c2 * g(n). In pratica, la funzione g(n) descrive il comportamento asintotico della funzione f(n), fornendo sia un limite superiore che uno inferiore.

Se il limite di f(n)/g(n) per n che tende a infinito esiste ed è un numero finito positivo, allora f(n) è O(g(n)).

Il termine con l'esponente più alto in un polinomio, trascurando le costanti.

Un numero reale positivo c e un intero non negativo n0, tali che per n ≥ n0 si ha |f(n)| ≤ c * |g(n)| .

Il limite di f(n)/g(n) per n che tende a infinito NON è finito. In altre parole, f(n) cresce più rapidamente di g(n).

Una funzione che contiene il termine dominante di f(n), che descrive la sua crescita asintotica.

Un polinomio della forma a_k * n^k + a_{k-1} * n^{k-1} + ... + a_1 * n + a_0.

La base del logaritmo.

La funzione log_a(n) cresce più lentamente di n per qualsiasi numero positivo a.

Una funzione f(n) è O(g(n)) se esiste una costante positiva c e un valore n0 tale che f(n) ≤ c * g(n) per tutti gli n ≥ n0. In sostanza, f(n) cresce al massimo allo stesso ritmo di g(n).

Una funzione f(n) è Ω(g(n)) se esiste una costante positiva c e un valore n0 tale che f(n) ≥ c * g(n) per tutti gli n ≥ n0. In sostanza, f(n) cresce almeno allo stesso ritmo di g(n).

Una funzione f(n) è Θ(g(n)) se esistono due costanti positive c1 e c2 e un valore n0 tale che c1 * g(n) ≤ f(n) ≤ c2 * g(n) per tutti gli n ≥ n0. In sostanza, f(n) cresce allo stesso ritmo di g(n).

La notazione Θ definisce una relazione di equivalenza tra funzioni. Questo significa che se f(n) è Θ(g(n)), allora g(n) è anche Θ(f(n)).

La notazione Ω definisce un preordine tra funzioni. Ciò significa che l'ordine non è necessariamente simmetrico.

Se il limite di f(n)/g(n) per n che tende all'infinito esiste ed è un numero reale positivo, possiamo concludere che f(n) è Θ(g(n)).

Se f(n) è Ω(g(n)) e f(n) è O(g(n)), allora f(n) è Θ(g(n)).

La notazione asintotica ci aiuta a capire il comportamento degli algoritmi per input di grandi dimensioni, ignorando le costanti e concentrandoci sul termine dominante della funzione.

Cambiare la base di un logaritmo equivale a moltiplicare per una costante. Ad esempio, log_a(n) = (log_b(n)) / (log_b(a)).

In O grande, la relazione f(n) ∈ O(g(n)) significa che f(n) cresce al massimo come g(n) per n che tende all'infinito.

La notazione O grande è un preordine, ovvero è una relazione riflessiva e transitiva. Riflessiva significa che f(n) ∈ O(f(n)). Transitiva significa che se f(n) ∈ O(g(n)) e g(n) ∈ O(h(n)), allora f(n) ∈ O(h(n)).

L'insieme O(g(n)) comprende tutte le funzioni che crescono al massimo come g(n). Quindi, funzioni come k, log2(n), n appartengono all'insieme O(n).

Il preordine in O grande genera una sequenza di inclusioni tra gli insiemi O. Ad esempio, O(1) ⊆ O(log n) ⊆ O(n) ⊆ O(n log n) ⊆ O(n^2).

La notazione O grande è utile per analizzare la complessità computazionale degli algoritmi. Permette di confrontare la velocità di crescita delle diverse operazioni e di identificare gli algoritmi più efficienti.

La notazione O grande è una notazione asintotica, ovvero descrive il comportamento delle funzioni quando n tende all'infinito. Non considera il comportamento delle funzioni per valori piccoli di n.