Algoritmi - analisi

Considerazioni sull'indirizzamento indiretto e l'accesso agli elementi di un array

Una seconda considerazione che ci può consentire di semplificare l'analisi riguarda l'indirizzamento indiretto o, in altri termini, la valutazione del costo dell'accesso agli elementi di un array. In molti casi è ragionevole supporre che le operazioni di gestione degli indici di un array (come incremento e decremento dell'indice) e lo stesso costo di accesso ai singoli elementi dell'array abbiano un costo unitario anziché logaritmico in funzione del valore dell'indice. Una motivazione per questa scelta è che il numero di elementi di un array indirizzabili, ad esempio, con una sola parola di 32 bit (e gestibili quindi con 32 operazioni di costo unitario) è 2 e quindi ampiamente sufficiente per tutte le applicazioni reali, in cui si tratta di gestire array di un numero di elementi nettamente inferiore.

Vediamo ora attraverso un ulteriore esempio come l'analisi a costi logaritmici possa...

esseresemplificata e come ci si possa ricondurre agli stessi risultati che si ottengono basandosisull'operazione dominante.

Esempio 1.11 Consideriamo nuovamente il programma di ordinamento chiamato insertionsort presentato nell'Esercizio 1.5. Esaminiamo innanzitutto il costo di esecuzione di taleprogramma istruzione per istruzione

1. log i ripetuta n - 1 volte
2. log i + log A[i] ripetuta n - 1 volte
3. log (i - 1) ripetuta n - 1 volte
4. 2 log j + log A [j] + log b ripetuta 1 +…+ (n-1) volte al più
5. log j + log A [j] ripetuta 1 +…+ (n-1) volte al più
6. log j ripetuta 1 +…+ (n-1) volte al più
7. log (j+1) + log b ripetuta n - 1 volte

Tenuto conto del fatto che i varia da 2 ad n, che nel caso peggiore j varia da i - 1 ad 1 e che, per ogni i, abbiamo A[i] A e b A otteniamo complessivamente che il tempo diMAX MAXesecuzione del predetto programma è t (n) (n - 1) ( 4 log n + 2 log A ) + j (4 log n + 3 log A )MAX

MAXj=1,n-1PCapitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.25 2Tenendo conto del fatto che j = n(n-1)/2 otteniamo l'espressione asintotica: O(nj=1,n-1(logn + log A ))MAXSe, come abbiamo detto precedentemente, facciamo l'ipotesi semplificativa che il valoreA sia considerato costante, otteniamo che il costo di esecuzione del programmaMAX 2insertion sort è t(n) = O (n log n)Se teniamo conto anche dell'ipotesi che il costo di gestione degli indici del vettore(aggiornamento degli indici, accesso agli elementi ecc.) sia da considerarsi unitario abbiamoun'ulteriore semplificazione. In tal caso infatti i costi delle istruzioni divengonorispettivamente1. 1 ripetuta n - 1 volte≤2. 1 + log A[i] 1 + log A ripetuta n - 1 volteMAX3. 1 ripetuta n - 1 volte≤4. 2+log A[j]+log b 2+2log A ripetuta 1 +…+ (n-1) volte al piùMAX≤5. 1 + log A[j] 1 + log AMAX ripetuta 1 +…+ (n-1) volte al più6. 1 ripetuta 1 +…+ (n-1) voltevolte al più 7. 1 + log b ripetuta n - 1 volte2e quindi il costo complessivo diviene t(n) = O(n ) che coincide con il costo determinato conl'analisi a costi uniformi.Come si è potuto vedere negli esempi forniti, esistono dunque circostanze (come nel caso dialgoritmi numerici basati su operazioni aritmetiche) in cui si rende necessario utilizzare ilmodello a costi logaritmici per evitare di fare un'analisi grossolana e imperfetta e altrecircostanze, più frequenti, in cui il modello a costi uniformi consente di ottenere unavalutazione sufficientemente accurata.Nel resto di questo Corso si farà sempre uso dell'approccio più semplice basato sul conteggio,a costi uniformi, delle istruzioni dominanti eseguite dal programma. Tuttavia non dobbiamosottovalutare il fatto che solo rendendoci conto del significato delle semplificazioni viste edella loro applicabilità possiamo essere certi di non avere trascurato nessun elementoimportante ai

fini di una corretta valutazione del programma.

Esercizio 6

Scrivi un programma in Java per determinare l'elemento massimo di un array; analizzane la complessità sia in modo esatto con il modello a costi logaritmici, sia tenendo conto delle ipotesi semplificative.

Capitolo 2 Strutture Dati Elementari (Bozza del % , ") ag. 2.265.

COMPLESSITÀ INTRINSECA DI PROBLEMI

5.1. Limiti inferiori e superiori alla complessità di un problema.

Quando abbiamo mostrato i diversi modi di procedere per giungere ad indovinare un numero compreso tra 1 ed n con il minimo numero di tentativi, abbiamo mostrato che un metodo basato sulla ricerca binaria consente di risolvere tale problema sistematicamente con un numero di tentativi O(log n). In tale occasione abbiamo anche osservato che il numero di 2 log n tentativi rappresenta una soglia al di sotto della quale non è possibile scendere. Tale 2  soglia è dovuta al fatto che il valore log n corrisponde alla

quantità di informazione necessaria per individuare un oggetto in un insieme di n oggetti. Esso corrisponde infatti al numero di bit necessari a rappresentare un qualunque numero compreso tra 0 ed n-1. Qualunque metodo generale per determinare un oggetto tra n oggetti, e che sia basato non sulla sorte ma su una sequenza sistematica di domande a risposta binaria, deve quindi necessariamente produrre, almeno nel caso peggiore, log n bit e comporta quindi log n tentativi. La soglia di complessità che abbiamo individuato è, in un certo senso, una misura della complessità intrinseca del problema dato. E' stato questo, dunque, il primo esempio di analisi della complessità intrinseca di un problema che abbiamo incontrato. Per semplice che esso sia possiamo utilizzarlo per fare alcune considerazioni. Per caratterizzare la complessità di un problema abbiamo bisogno, fondamentalmente, di due riferimenti. Prima di tutto dobbiamo sapere quale è,

nel caso peggiore, la quantità di tempo (o di memoria) sufficiente per la risoluzione del problema dato. Questa quantità rappresenta un limite superiore (un upper bound) della complessità del problema. A tal fine è sufficiente conoscere qualche algoritmo (non necessariamente il migliore) per la risoluzione del problema dato e valutarne la complessità con uno dei metodi visti nelle sezioni precedenti.

La conoscenza di un upper bound, tuttavia, non ci dà un'informazione completa sulla complessità del problema, infatti potrebbero esistere metodi di risoluzione del problema dato diversi da quelli noti che ne consentono la soluzione in modo molto più rapido. Sapere che un problema è risolubile con un algoritmo di costo esponenziale, ad esempio, non ci dice molto sulla reale complessità del problema che, al limite, potrebbe essere anche lineare.

L'informazione data dall'upper bound deve dunque essere confrontata con

una limitazione inferiore (un lower bound) cioè con un'indicazione della quantità di tempo (o di memoria) che, sempre nel caso peggiore, è sicuramente necessaria (anche se non sufficiente) per la risoluzione del problema. E' qui che interviene il concetto di complessità intrinseca del problema. Per determinare un lower bound di complessità di un problema è necessario, infatti, dimostrare che nessun algoritmo per la risoluzione del problema stesso può fare a meno di utilizzare una certa quantità di risorsa (tempo, memoria) o di eseguire un certo numero di operazioni (ad esempio quadratico) almeno in una serie di casi particolarmente difficili. Per rappresentare un upper bound e un lower bound di complessità di un problema si usano notazioni simili a quella adottata per la complessità di un algoritmo. Sia data una qualunque misura di

complessità per un dato modello di macchina (numero di operazioni dominanti, quantità di tempo, quantità di memoria ecc.); sia n la dimensione del problema dato e sia t(n) il costo di esecuzione di un algoritmo A nel caso peggiore, cioè in A corrispondenza della più difficile tra le istanze di dimensione n.

Definizione 1.3: Un problema ha un limite superiore (upper bound) di complessità O(g(n)) se esiste un algoritmo A per la sua risoluzione che ha un costo di esecuzione O(g(n)), cioè esistono c ed m tali che t(n) ≤ c g(n) per n ≥ m.

Definizione 1.4: Un algoritmo A ha un limite inferiore (lower bound) di complessità Ω(g'(n)) se esistono c ed m tali che t(n) ≥ c g'(n) per n ≥ m, cioè, asintoticamente, il costo di esecuzione dell'algoritmo, nel caso peggiore, è sempre maggiore o uguale di c g'(n). Un problema ha un limite inferiore (lower bound) di complessità Ω(g'(n)) se,

esso ha una complessità (g'(n)). Chiaramente, tanto più vicine sono le funzioni g e g', tanto più precisa sarà la caratterizzazione della complessità del problema dato. Ad esempio, per il caso della moltiplicazione di matrici n x n, è stato dimostrato che la complessità del problema (misurata in termini di moltiplicazioni tra elementi) è O(n^2). Se si vuole pervenire ad una più precisa caratterizzazione, è necessario o individuare un algoritmo che richieda meno di n^2 operazioni oppure dimostrare che la complessità intrinseca del prodotto di matrici è maggiore di quanto osservato finora e che ogni algoritmo per questo problema richiede necessariamente più di n^2 operazioni (ne richiede ad esempio n log n oppure n^3). Quando si riesce a mostrare che un problema ha una complessità O(g) e (g') con g e g'

g' asintoticamente uguali a meno di costanti moltiplicative (cioè lim g/g' = c > 0) possiamo dire che la complessità del problema è determinata con precisione. In questo caso usiamo una notazione opportuna.

Definizione 1.5 Dato un algoritmo A, se il suo costo è O(g(n)) e il suo lower bound è Ω Θ(g(n)) diciamo che la sua complessità è Θ(g(n)), cioè, per opportune c, c ed m, per n ≥ m1 2 ≤ ≤ abbiamo c g(n) ≤ t(n) ≤ c g(n). Dato un problema, se il suo upper bound è O(g(n)) e il suo lower bound è Ω(g(n)), diciamo che la sua complessità è Θ(g(n)).

Il problema dell'individuazione di un numero compreso tra 1 ed n è un esempio di problema la cui complessità può essere nettamente caratterizzata. I