piccole sottosequenze crescono

[fph]

Direttamente da un corso di informatica dell'UniPI:

Gli dei, nella loro infinita bontà, ci hanno dato una sottosequenza di numeri interi, ad esempio
6 10.000 2 3 37 5 39 11 29 13 14 1
Trovate un algoritmo che ne determini la più lunga sottosequenza crescente (formata da termini anche non consecutivi), ad esempio in questo caso 2 3 5 11 13 14.
Quanto velocemente (nel senso di "O grande di qualcosa") si riesce a fare?

[stefano88]

Per ogni numero segno la lunghezza della sottosequenza più lunga che finisce con quel numero e l'indice (a partire da zero intendendolo come un array C) del numero che lo precede.
Per ogni numero n bisogna scorrere tutti i numeri precedenti minori di n e trovare quello con la massima lung. di sottosequenza possibile.
1° passaggio (6):
Lung: 1; Prec: -1;
2° passaggio (10000):
Lung: 2; Prec: 0;
3° passaggio (2):
Lung: 1; Prec: -1;
4° passaggio (3):
Lung: 2; Prec: 2;
5° passaggio (37):
Lung: 3; Prec: 3;
6° passaggio (5):
Lung: 3; Prec: 3;
7° passaggio (39):
Lung: 4; Prec: 4;
8° passaggio (11):
Lung: 4; Prec: 5;
9° passaggio (29):
Lung: 5; Prec: 7;
10° passaggio (13):
Lung: 5; Prec: 7;
11° passaggio (14):
Lung: 6; Prec: 9;
12° passaggio (1):
Lung: 1; Prec: -1;

Quindi il numero alla posizione 10 termina la più lunga sottosequenza, andando a ritroso si trovano pure gli altri numeri.
Il tempo calcolatelo voi che io non ci sono buono.

[Haurio]

La prima soluzione che mi viene in mente è una semplice quadratica...ci sono parecchi accorgimenti che si possono adottare al fine di ridurre la velocità del programma ma il tempo asintotico è O(n^2)

[fph]

Anche l'algoritmo di Stefano è in $ O(n^2) $: infatti ad ogni passo bisogna controllare tutti i numeri precedenti, quindi il primo numero impiega tempo "0", il secondo "1", il terzo "2" (unità arbitrarie, se vuoi puoi vederle come il costo del numero di "operazioni elementari" che servono) e così via: in totale,
$ 1+2+3+\ldots+n= \frac{n(n+1)}{2}=O(n^2) $.

Ora però provate a trovare qualcosa di più veloce, si riesce a scendere sotto $ O(n^2) $...

[urano88]

Questo è il mio algoritmo, non formalizzato in nessun linguaggio, senza tempo calcolato (non ne sono capace ). In ogni caso mi pare che sia veloce e che funzioni (ho provato su diverse stringhe)...

1) divido la sequenza divina in diverse sottosequenze di numeri crescenti consecutivi (e le nomino partendo da sinistra con lettere maiuscole)
2) considero la sequenza A e il primo numero della sequenza B
3) calcolo il numero di elementi che dovrei eliminare da A partendo da destra per fare in modo che l'ultimo numero di A sia minore del primo numero di B
4) se quel numero è minore o uguale al numero di elementi di B allora cancello gli elementi e giunto A con B, altrimenti cancello A
5) rinomino le sottosequenze e, se esiste una sottosequenza B, torno al passaggio 2, altrimenti ho finito

Fatemi sapere com'è...

[fph]

1) divido la sequenza divina in diverse sottosequenze di numeri crescenti consecutivi (e le nomino partendo da sinistra con lettere maiuscole)

come lo fai? In casi un po' "incasinati" non è chiaro come questo si faccia in modo univoco

[urano88]

posto un esempio scritto a mano (spero si capisca bene):



ma comunque ho già trovato una stringa che mette in crisi l'algoritmo, ad esempio:
100 101 102 103 1 2 12 3 4 11 5 6 10
il mio algoritmo cancellerebbe la stringa B (dato che dovrei cancellare 4 elementi dalla A per poterle unire) e allo stesso modo cancellerebbe la C e la D lasciando come sequenza
100 101 102 103
quando invece la maggiore è
1 2 3 4 5 6

oppure anche questa:
9 10 11 12 1 13 14 2 15 16 3
dove resta 9 10 11 12 invece di 9 10 11 12 13 14 15 16

ho provato a correggerlo ma mi sembra che si complichi (e allunghi) molto...

[alexp]

non so calcolare con precisone O, ma può diventare minore di O(n^2) se consideriamo che se, per esempio, partendo dal 1° elemento troviamo una sequenza lunga 2 allora dobbiamo analizzare solo fino all'elemento n-2. si capisce?

[fph]

non so calcolare con precisone O, ma può diventare minore di O(n^2) se consideriamo che se, per esempio, partendo dal 1° elemento troviamo una sequenza lunga 2 allora dobbiamo analizzare solo fino all'elemento n-2.

Mi sembra di no, l'ultimo elemento lo devi "guardare" comunque perché potresti avere senza di esso molte sottosequenze della stessa lunghezza, e devi capire a quali di queste puoi "attaccare" l'ultimo elemento.

Ah, e poi: solitamente quando non si specifica altro le analisi di complessità si intendono "al caso peggiore". Quindi quello che vi sto proponendo è di trovare un algoritmo che a partire da /tutte/ le sottosequenze possibili ha una lunghezza in istruzioni elementari che cresce (rispetto a n) meno di O(n^2), dove n è la lunghezza della sequenza iniziale.

Non è facilissimo ma (secondo me) è divertente.Buon lavoro...

[CUCU]

Io userei la programmazione dinamica in combinazione con alberi di ricerca.
Ogni elemento dell'array punterà all'elemento che lo precede nella sequenza ascendente più lunga.
Per trovare quest'ultima basta trovare l'elemento di valore più grande nell'array minore o eguale ad esso che lo precede (per "precede" intendo che ha indice nell'array minore di esso).
Se ad ogni passo inseriamo in un albero binario di ricerca gli elementi possiamo trovare l'elemento di valore massimo minore o uguale a quello in questione in tempo O(logn).
In tal modo abbiamo un algoritmo di tempo O(nlogn).
però come adattare gli alberi di ricxerca a questo problema?
o forse si devono calcolare i prefissi di qualcosa?
mah...ci penserò
Saluti

[CUCU]

Inoltre aggiungo che per "meno di O(n^2)" in Informatica si suole usare la notazione o(n^2), con la "o" minuscola in luogo della Big-oh.

[fph]

Io userei la programmazione dinamica in combinazione con alberi di ricerca.
Ogni elemento dell'array punterà all'elemento che lo precede nella sequenza ascendente più lunga. Per trovare quest'ultima basta trovare l'elemento di valore più grande nell'array minore o eguale ad esso che lo precede (per "precede" intendo che ha indice nell'array minore di esso). Se ad ogni passo inseriamo in un albero binario di ricerca gli elementi possiamo trovare l'elemento di valore massimo minore o uguale a quello in questione in tempo O(logn). In tal modo abbiamo un algoritmo di tempo O(nlogn).

Ciao! Idea buona ma mi sembra che ci sia ancora qualcosa che non va. Per esempio, se c'è la sequenza 11 22 1 2 3 35, se ho ben capito il tuo algoritmo attacca il 35 all'elemento di valore più grande che lo precede, cioè alla sequenza 11 22 invece che alla 1 2 3.
Ah, e gli alberi binari almeno nella mia soluzione non servono. Si fa tutto solo con i cari vecchi array, senza "cannoni".

[CUCU]

Forse l'ho trovato, ditemi voi se sia corretto.

Mantengo un'array b di lunghezza n, dove n è la lunghezza dell'array a contenente l'input.
Inizialmente l'array b è inizializzato per esempio a -1, tranne che b[1]=a[1].

j=1

Per i =2 to n {
flag =0
for z=1 to j
se a<b[j] allora {
b[j]=a
flag=1
termina ciclo;
}
if (flag=0){ j=j+1;
b[j]=a
}
}
restituisci j (j sarà il valore della più lunga sequenza ascendente)

Questo algoritmo dovrebbe avere tempo O(n*l) dove l è il valore cercato.
Cioè funziona così:
Immaginiamo che invece che b[] sia un array sia invece un array di array, per esempio un array dove ogni elemento è uno stack.
All'inizio poniamo il primo elemento di a nel primo stack.
Se il a[2] è maggiore del primo elemento del primo stack allora lo aggiungiamo al primo stack perché la sequenza cresce. Altrimenti creiamo un secondo stack e ce lo mettiamo dentro.
E così via.
Così alla fine il valore che cerchiamo è pari al numero di stack creati.
Ovviamente ho parlato di stack solo per rendere più intuitivo l'algoritmo ma non c'è bisogno di creare nessuno stack, e basta memorizzare solo il top di ogni stack che è l'unico valore che ci serve.

Nota che così troviamo solo il valore, se vogliamo dare in output la sequenza possiamo modificare leggermente l'algoritmo aggiungo un array di puntatori all'indietro.
Ovviamente in questo modo il caso peggiore è sempre quadratico se l=n, ma è lineare se l è una costante.
MA possiamo raffinare l'algoritmo usando la ricerca binaria?

[CUCU]

Io userei la programmazione dinamica in combinazione con alberi di ricerca.
Ogni elemento dell'array punterà all'elemento che lo precede nella sequenza ascendente più lunga. Per trovare quest'ultima basta trovare l'elemento di valore più grande nell'array minore o eguale ad esso che lo precede (per "precede" intendo che ha indice nell'array minore di esso). Se ad ogni passo inseriamo in un albero binario di ricerca gli elementi possiamo trovare l'elemento di valore massimo minore o uguale a quello in questione in tempo O(logn). In tal modo abbiamo un algoritmo di tempo O(nlogn).

Ciao! Idea buona ma mi sembra che ci sia ancora qualcosa che non va. Per esempio, se c'è la sequenza 11 22 1 2 3 35, se ho ben capito il tuo algoritmo attacca il 35 all'elemento di valore più grande che lo precede, cioè alla sequenza 11 22 invece che alla 1 2 3.
Ah, e gli alberi binari almeno nella mia soluzione non servono. Si fa tutto solo con i cari vecchi array, senza "cannoni".

Sì infatti per ciò dicevo "adattando gli alberi" perché ovviamente bisognerebbe trovare un metodo ad-hoc.

Il nuovo algoritmo che ho postato assomiglia al tuo?

[CUCU]

Forse l'ho trovato, ditemi voi se sia corretto.

Mantengo un'array b di lunghezza n, dove n è la lunghezza dell'array a contenente l'input.
Inizialmente l'array b è inizializzato per esempio a -1, tranne che b[1]=a[1].

j=1

Per i =2 to n {
flag =0
for z=1 to j
se a<b[j] allora {
b[j]=a
flag=1
termina ciclo;
}
if (flag=0) j=j+1;
}
restituisci j (j sarà il valore della più lunga sequenza ascendente)

Questo algoritmo dovrebbe avere tempo O(n*l) dove l è il valore cercato.
Cioè funziona così:
Immaginiamo che invece che b[] sia un array sia invece un array di array, per esempio un array dove ogni elemento è uno stack.
All'inizio poniamo il primo elemento di a nel primo stack.
Se il a[2] è maggiore del primo elemento del primo stack allora lo aggiungiamo al primo stack perché la sequenza cresce. Altrimenti creiamo un secondo stack e ce lo mettiamo dentro.
E così via.
Così alla fine il valore che cerchiamo è pari al numero di stack creati.
Ovviamente ho parlato di stack solo per rendere più intuitivo l'algoritmo ma non c'è bisogno di creare nessuno stack, e basta memorizzare solo il top di ogni stack che è l'unico valore che ci serve.

Nota che così troviamo solo il valore, se vogliamo dare in output la sequenza possiamo modificare leggermente l'algoritmo aggiungo un array di puntatori all'indietro.
Ovviamente in questo modo il caso peggiore è sempre quadratico se l=n, ma è lineare se l è una costante.
MA possiamo raffinare l'algoritmo usando la ricerca binaria?

Sì usiamo la ricerca binaria in questo modo:
invece che scandire tutto l'array j, manteniamo anche un albero binario di ricerca
e ad ogni passo cerchiamo se esiste nell'albero un valore minore di b[j], se esiste allora settiamo la flag=1 come nell'algoritmo precedente.

In questo modo il tempo scende a O(nlogl), dove l è il valore cercato.
Anzi ora che ci penso non abbiamo bisogno più di b nella forma di array, che diventa astrattamente un albero di ricerca.