Introduzione alla notazione asintotica

Cercare di definire il tempo impiegato da una funzione per essere eseguita in termini di DIMENSIONE dell’input. **(il numero di bit a livello basso basso)

Ma abbiamo il problema di misura, in quanto dobbiamo considerare delle variabili che siano indipendenti rispetto alla macchina.

Caratteristiche della notazione

Vogliamo considerare una notazione asintotica (che guarda quanto fa il comportamento verso l’infinito)

### Accesso di memoria Ogni operazione in un processore moderno ha in generale un numero di accessi in memoria constante (solitamente abbiamo sempre un numero fissato di operandi possibile, questo significa che se un certo algoritmo ha una certa complessità, resta di questa complessità anche tenendo in considerazione le operazioni di accesso di memoria).

Questo discorso non tiene più se teniamo in considerazione numeri a precisione infinita, che possono avere un numero arbitrario di accessi in memoria per poter essere computato.

Funzione di costo

Solitamente teniamo in considerazione nel conteggio di costo solamente le operazioni utili per computare matematicamente la funzione. In realtà ci sono delle operazioni di accesso di memoria nascoste che solitamente non vediamo.

Solitamente andiamo a definire la performance di un certo algoritmo in una certa architettura come:

$$ \text{ performance } = \frac{\text{ operazioni elementari }}{\text{ tempo di esecuzione }} $$

Questo si chiama flops per secondo, ed è l’unità di memoria utilizzata solitamente. Possiamo andare a confrontare l’upper bound di performance di un algoritmo su un processore usando la performance massima data dal produttore. Solitamente secondo il professore si arriva a circa 30% di performance del processore per una cosa molto buona.

Contare le operazioni

Il conteggio delle operazioni è un modo possibile per contare il costo di certe implementazioni di algoritmi.

Identifichiamo tree metodi principali per andare a contare gli algoritmi:

• Conteggio delle operazioni elementari: Contare le operazioni di base che vengono eseguite (somma, moltiplicazione, confronto, assegnamento)
• Codice strumentale: codice esterno che conta quando certi eventi avvengono o meno.
• Performance counters: strumenti ad hoc che vanno a contare questo genere di cose (cache miss, cicli di clock e simili).

Modelli asintotici

Abbiamo trattato di o-piccolo e ogrande in Analisi.

O-grande

$$ f(n) \leq c g(n) $$

Ossia: la funzione è upper-bounded per numeri molto grandi. Quando vale la versione stretta si può dire che è anche o-piccolo.

$$ n^{c}, 2^{O(\log n)}, n^{O(1)} $$

Sono equivalenti.

o-piccolo

Usiamo la definizione trattata in Analisi:

Θ (Theta)

$$ c_1 g(n) \leq f(n) \leq c_2 g(n) $$

Questo implica che $f(n)$ cresce alla stessa velocità di $g(n)$ per valori di $n$ sufficientemente grandi.

Alcune proprietà della notazione $\Theta$:

• Se $f(n) = \Theta(g(n))$, allora $f(n)$ è sia $O(g(n))$ che $\Omega(g(n))$.
• La notazione viene usata per descrivere il comportamento preciso della funzione, senza una sovrastima (come $O$) o una sottostima (come $\Omega$).

Ω-grande

$$ f(n) \geq c g(n) $$

Questo significa che $f(n)$ cresce almeno alla stessa velocità di $g(n)$ per valori grandi di $n$.

ω-piccolo

$$ f(n) > c g(n) $$

Ciò implica che $f(n)$ cresce strettamente più velocemente di $g(n)$, ovvero non esiste un limite superiore costante per il loro rapporto.

Costo e Complessità computazionale

Definizioni

Analisi ammortizzata

Introduzione

Questa è una tecnica che trova il costo medio di un algoritmo. La differenza con il calcolo del costo medio classico è che questo calcolo mi trova il costo medio per una sequenza di operazioni mentre il classico mi trova il costo medio per una singola operazione

Casi di utilizzo

Di solito è utile utilizzare questo metodo di analisi in queste condizioni

1. Caso pessimo non frequente (quindi per dire che nella media un algoritmo è molto più efficiente)
2. Semplificare l’analisi del caso medio

Aggregazione

Vogliamo cercare un limite superiore su n operazioni, poi dividere il tutto per n. Questo è più utile quando il costo totale è conosciuto

Accantonamenti

Questo è basato sulla contabilità, ho un certo credito iniziale, posso utilizzare tutto, ma non posso mai andare in negativo.

Questo è utile quando ci sono diverse operazioni.

Un esempio di analisi ammortizzata utilizzando gli accantonamenti è la doubling and halving in cui 3 monete per ogni operazione di inserimento bastano poi per ricopiare ed espandere o diminuire il tutto a piacere (quindi 3n , si ha un costo costante). menti è la doubling and halving in cui 3 monete per ogni operazione di inserimento bastano poi per ricopiare ed espandere o diminuire il tutto a piacere (quindi 3n , si ha un costo costante).

Registro Ripassi

14/03/2024	Ripassato per Time and Space Complexity

Ripasso Prox: 31 Ripasso: May 28, 2022 Ultima modifica: April 28, 2022 5:07 PM Primo Abbozzo: February 24, 2022 9:19 AM Stato: 🌕🌕🌕🌕🌕 Studi Personali: No