Algoritmi e strutture di dati - esempio tesina find-maximum-subarray

Una soluzione più efficiente utilizzando il metodo del divide ed impera

Vediamo come possiamo risolvere il problema del massimo sub-array utilizzando il metodo del divide ed impera:

• Array di partenza A [l .. R];
• Definisco mid = floor(R+L/2);
• Divido A in due sotto-array A[l .. mid] e A[mid+1 .. R]

Il massimo sub-Array deve trovarsi esattamente in una delle seguenti posizioni:

1. Interamente nel sotto array di sx;
2. Interamente nel sotto array di dx;
3. Che passa per il punto di mezzo.

Possiamo allora trovare i massimi sottoarray del sottoarray di sx e di dx in modo ricorsivo, in quanto questi due sotto-problemi sono istanze più piccole del problema di trovare un massimo sottoarray. Quindi, quello che rimane da fare è di trovare un massimo sotto array che passa per il punto di mezzo e, fra i tre sottoarray, prendere quello con somma maggiore.

Massimo sotto-vettore passante per il

<center>
    <ul>
        <li>Find-Max-Crossing-SubArray(A,l,m,h)</li>
    </ul>
    left-sum = -inf
    sum = 0
    for i = m downto l
        sum = sum+A[i]
        if sum > left-sum
            left-sum = sum
            max-left = i
    right-sum = -inf
    sum = 0
    for j = m + 1 to h
        sum = sum + A[j]
        if sum > right-sum
            right-sum = sum
            max-right = j
    return(max-left,max-right,left-sum+right-sum)
</center>

<p>Questa procedura opera nel seguente modo, il primo for trovare il massimo sotto-array
nella metà di sinistra. Poiché questo sottoarray deve contenere A[m], il ciclo for inizia con
l'indice i a mid e procede per valori decrescenti dell'indice fino ad arrivare a l (low),
cosicché ogni sottoarray che considererà è della forma A[i .. m]. Le prime 2 righe
inizializzano le variabile left-sum, che contiene la somma più grande fino ad ora trovata, e
sum, che contiene la somma degli elementi di A[i .. m]. Quando troviamo (riga 5) un
sottoarray A[i .. m] con una somma maggiore di left-sum, aggiorniamo left-sum con la
somma di questo sottoarray e poi
</p>

aggiorniamo max_left, per memorizzare l'indice. Il secondo ciclo for esegue, in modo duale, lo stesso procedimento sul sotto array dx. Disponendo ora della procedura Find-Max-Crossing-SubArray, possiamo scrivere il pseudocodice di un algoritmo divide ed impera per risolvere il problema del massimo sotto-array.

Trova il massimo sub.array
Find-Max-Subarray(A,l,h)
1 if h == l
2 return (l,h,A[l])
3 else m = floor( (l+h)/2)
4. (left-l,left-h,left-sum) = Find-Max-Subarray(A,l,m)
5. (right-l,right-h,right-sum) = Find-Max-Subarray(A,m+1,h)
6. (cross-l,cross-h,cross-sum) = Find-Max-Crossing-Subarray(A,l,m,h)
7. if (left-sum >= right-sum and left-sum >=cross-sum)
8. return (left-l,left-h,left-sum)
9. else if (right-sum >= left-sum and right-sum >=cross-sum)
10. return(right-l,right-h,right-sum)
11. else return (cross-l,cross-h,cross-sum)

La chiamata iniziale di FIND_MAXIMUM-SUBARRAY(A,1,A.length) troverà un massimo sottoarray di A[1 .. n]. Come FIND-MAX-CROSSINF-SUBARRAY, anche laprocedura ricorsiva FIND-MAXIMUM-SUBARRAY restituisce una tupla contenente gli indici che delimitano un massimo sub-array, insieme con la somma dei valori di un massimo sottoarray. La riga 1 verifica il caso base, dove il sottoarray ha un solo elemento. Un sottoarray con un solo elemento ha un unico sottoarray - sé stesso - e quindi la riga 2 restituisce una tupla con gli indici iniziale e finale dell'unico elemento, insieme con il suo valore. Le righe 3-11 gestiscono il caso ricorsivo. La riga 3 esegue la parte divide, calcolando l'indice m nel punto di mezzo. Chiamiamo A[l .. m] il sottoarray sx e A[m+1 .. h] il sotto-array dx. Poiché adesso sappiamo che il sottoarray A[l.. h] contiene almeno due elementi, ciascuno dei sottoarray sx e dx deve avere almeno un elemento. Le righe 4-5 eseguono la parte impera, trovando ricorsivamente i massimi sottoarray all'interno dei sottoarray sx e dx, rispettivamente. Le righe 6-11 formano la parte combina.

riga 6 trova un massimo sottoarray che passa per il punto di mezzo. La riga 7 verifica se il sottoarray sx contiene un sottoarray con la somma massima e la riga 8 restituisce tale sottoarray, altrimenti, la riga 9 verifica se il sottoarray dx contiene un sottoarray con la somma massima, e la riga 10 restituisce tale sottoarray. Se nessuno dei due, sx e dx, contiene un sottoarray con la somma massima, allora un massimo sottoarray dovrà passare per il punto di mezzo, e la riga 11 lo restituisce.

D. Soluzione Lineare

Come ultima soluzione al problema, mostriamo un algoritmo che lo risolvere in maniera lineare con costanti moltiplicative molto piccole (come poi si vedrà, questa versione è quella che è sempre preferibile come scelta).

Algoritmo Lineare

Linear( )

1 int maxSum = -inf;

2 i=j

3 thisSum = 0;

4 for j = l to h

5 thisSum += A[ j ];

6 if thisSum > maxSum

7 maxSum = thisSum;

8 maxL = i;

9 maxR = j;

10 else if thisSum < 0

11 i = j + 1;

12 thisSum = 0;

0;return(maxL,MaxR,maxSum);

L'algoritmo somma sequenzialmente tutti gli elementi del vettore di ingresso, quando si verifica che la somma degli elementi è maggiore della somma massima aggiorna la somma massima e gli indici. Se si verifica che la somma parziale è minore di zero, l'indice i viene posto all'indice immediatamente superiore a quello del ciclo e si inizializza al valore zero la somma parziale. L'idea è che se una serie di elementi è tale da far diventare la somma parziale zero, il vettore massimo deve per forza trovarsi prima o dopo questa serie di elementi.

Analisi della complessità

Per descrivere la complessità di un algoritmo utilizzeremo la notazione asintotica. Tale notazioni sono comode per descrivere la funzione T(n), tempo di esecuzione nel caso peggiore, che di solito è definita solo per dimensioni intere dell'input.

Per una data funzione g(n), indichiamo con l'insieme delle funzioni = {

f(n) : esistono delle costanti positive c, c' e n tali che 1 <= c * g(n) <= f(n) <= c' * g(n) per ogni n

Si dice che g(n) è un limite asintoticamente stretto per f(n).

Per una data funzione g(n), indichiamo con O(g(n)) l'insieme delle funzioni f(n) : esistono una costante positiva c e n tali che 0 <= f(n) <= c * g(n) per ogni n

Si dice che g(n) è un limite asintotico superiore per f(n).

Per una data funzione g(n), indichiamo con Ω(g(n)) l'insieme delle funzioni f(n) : esistono una costante positiva c e n tali che 0 <= c * g(n) <= f(n) per ogni n

Si dice che g(n) è un limite asintotico inferiore per f(n).

Diamo ora delle semplici regole generali:

• La complessità di un algoritmo è pari alla somma delle complessità delle istruzioni che lo compongono.
• Le operazioni elementari (confronto, assegnazione, lettura di una variabile, stampa di una variabile) hanno complessità O(1). Questa assunzione non è totalmente corretta, considerato che ogni variabile occupa un numero di byte proporzionale al suo

valore e sarebbe quindi più sensato pensare che la complessità di un'operazione come quella di lettura/scrittura di una variabile sia proporzionale al logaritmo del suo valore; tuttavia è da tener presente che la complessità computazionale va calcolata per valori molto grandi dell'input e quindi, come vedremo nel seguito, questa assunzione non fa variare sensibilmente il risultato.

L'istruzione IF (condizione) THEN istruzione1 ELSE istruzione2 ha complessità pari al massimo delle complessità di istruzione1 ed istruzione2, se si può assumere che la complessità di condizione sia costante.

Le iterazioni (cicli WHILE e REPEAT) hanno complessità pari alla massima complessità delle istruzioni all'interno del ciclo moltiplicata per il numero di volte per cui quel ciclo viene ripetuto. Questa regola produce un risultato utile se tutte le iterazioni del ciclo hanno la stessa complessità e se

è possibile stimare in modoabbastanza preciso il numero di iterazioni.

A. Complessità dell’ algoritmo brute force cubico

Per le regole dette sopra, nell’algoritmo troviamo, alla linea 2,3 e 5, tre cicli for tra di loroinnestati che fanno un (n) confronti. La complessità computazionale dell’algoritmo sarà(n^3).

B. Complessità dell’ algoritmo brute force quadratico.

In modo equivalente ha quanto fatto sopra possiamo dire che la complessità di questoalgoritmo sarà (n^2) , in quanto troviamo 2 cicli for innestati che fanno un (n) confronti.

C. Complessità del metodo ricorsivo.

Per valutare la complessità di un algoritmo ricorsivo ci possiamo avvalere di tre metodi, ilteorema dell’esperto, il metodo della ricorsione ed il metodo della sostituzione. 10Prima di analizzare la funzione ricorsiva, analizziamo la complessità dl metodo FIND-MAX-ROSSING-SUBARRAY, se il vettore A contiene n elementi,

Eseguo due cicli for con complessità (n), per la regola della somma il costo della funzione è (n). A questo punto, costruiamo una ricorrenza che descrive il tempo di esecuzione della procedura ricorsiva FIND-MAXIMUM-SUBARRAY. Supponiamo, senza perdere di generalità, che la dimensione dell'array sia un multiplo di 2, cosicché le dimensioni di tutti i sotto problemi sono numeri interi. Indichiamo con T(n) il tempo di esecuzione della FIND_MAXIMUM-SUBARRAY su un sotto-array di n elementi. Per cominciare, la riga 1 richiede un tempo costante. Il caso base, quando n = 1, è semplice: la riga 2 richiede un tempo costante e quindi T(1) = (1). Il caso ricorsivo si verifica quando n > 1. Le righe 1 e 3 richiedono un tempo costante. Ciascun sotto-problema, riguarda un sottoarray di n/2 elementi; quindi occorre un tempo T(n/2) per risolvere ciascun sotto-problema. Poiché dobbiamo risolvere due sotto-problemi, il contributo delle righe 4 e 5 è pari a 2T(n/2).

La riga sei costa (n).
Ricapitolando
Risoluzione con metodo dell'esperto:
Il metodo dell'esperto si può utilizzare quando la ricorsione si presenta nella forma
T(n) = a*T(n/b) + f(n)
Con a >= 1, b > 1 e f(n) una funzione asintoticamente positiva. La nostra ricorsione soddisfa questi criteri. T(n), precisamente, rientra nel secondo caso del teorema dell'esperto, cioè:
T(n) = O(n^log_b(a))
se f(n) = O(n^c) con c < log_b(a).
Nel nostro caso a = > è verificata la condizione. Allora la complessità dell'algoritmo sarà O(n^log_b(a)).
Risoluzione con metodo della sostituzione:
Il metodo della sostituzione per risolvere la ricorrenza richiede due passi:
- Ipotizzare la forma della soluzione
- Usare l'induzione matematica per trovare costanti e dimostrare che la soluzione funziona
Il nome del metodo deriva dalla sostituzione della soluzione ipotizzata al posto d