04: Tempo di Calcolo e Complessità Asintotica

True (A)

Il numero di operazioni eseguite da un algoritmo con x in input.

<p>max T0(x)</p> Signup and view all the answers

<p>Caso migliore = Numero minimo di operazioni per un input di dimensione n Caso peggiore = Numero massimo di operazioni per un input di dimensione n Insertion-Sort = Algoritmo di ordinamento con operazioni variabili Selection-Sort = Algoritmo di ordinamento più complesso nel caso peggiore</p> Signup and view all the answers

<p>Determinare quante risorse utilizza (D)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>O grande, O piccolo, Omega.</p> Signup and view all the answers

<p>La crescita di una funzione trascurando costanti moltiplicative. (C)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>T(n) = an + b</p> Signup and view all the answers

<p>D0</p> Signup and view all the answers

<p>D0 = 2 + D (B)</p> Signup and view all the answers

<p>T(n) = a2 n^2 + a1 n + a0 con a2 &gt; 0</p> Signup and view all the answers

<p>T(n) = an + b = Crescita lineare T(n) = a2 n^2 + a1 n + a0 = Crescita quadratica f(n) ∈ O(g(n)) = Limite superiore c &gt; 0 = Costante positiva</p> Signup and view all the answers

<p>≤</p> Signup and view all the answers

<p>O (grande O) (C)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>f(n) è limitata superiormente da g(n).</p> Signup and view all the answers

<p>Ω (omega grande)</p> Signup and view all the answers

<p>O = Limite superiore Θ = Limiti stretti Ω = Limite inferiore f(n) = Funzione da analizzare</p> Signup and view all the answers

<p>n ∈ O(2n) (A)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Costanti positive utilizzate per stabilire i limiti per la funzione f(n).</p> Signup and view all the answers

<p>Il cambio di base dei logaritmi comporta la moltiplicazione per una costante. (D)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>preordine</p> Signup and view all the answers

<p>log(n) = Crescita lenta n = Crescita lineare n^2 = Crescita quadratica e^n = Crescita esponenziale</p> Signup and view all the answers

<p>k (A), log2 n (D)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>insiemistica</p> Signup and view all the answers

<p>Se $0 &lt; a &lt; u$, allora $f(n) ext{ è } O(g(n))$. (B)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Θ è riflessiva, transitiva e simmetrica. (A)</p> Signup and view all the answers

<p>2n^2</p> Signup and view all the answers

<p>ak</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>$85n + 123$ = $O(n)$ $2n^2 + n + 10$ = $O(n^2)$ $5n + ext{log}_2 n + 5$ = $O(n)$ $n + 25 ext{log}_2 n + 5$ = $O( ext{log}_2 n)$</p> Signup and view all the answers

<p>f(n) e g(n) crescono con lo stesso tasso asintotico.</p> Signup and view all the answers

<p>È in $O(n^k)$. (C)</p> Signup and view all the answers

<p>Θ</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>O = Limite superiore della crescita di una funzione Ω = Limite inferiore della crescita di una funzione Θ = Indica che due funzioni crescono allo stesso tasso f(n) ∈ Θ(g(n)) = f(n) è asintoticamente equivalente a g(n)</p> Signup and view all the answers

<p>ak &gt; 0</p> Signup and view all the answers

<p>Se f(n) ∈ Θ(g(n)), allora f(n) è limitata superiormente e inferiormente da g(n). (C)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>f(n) e g(n) devono avere lo stesso tasso di crescita asintotica.</p> Signup and view all the answers

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.