View Full Version : Piccolo problema di algoritimi
qwerty86
16-02-2009, 15:53
Salve ragazzi sto studiando Algoritmi e strutture dati e mi sono imbattuto in questo problema.
Descrivere ed analizzare un algoritmo che, in tempo O(n log n), dato un insieme S di numeri interi e un altro intero x, determini se esistono due elementi in S la cuimedia aritmetica è esattamente x
Non tenendo conto del tempo di esecuzio è semplice trovare un algoritmo, bastano due cicli innestati e controllare le coppie a una a una...il problema è proprio il requisito relativo al tempo di esecuzione O (n log n). Ci sto pensando da due giorni ma non riesco a trovare una soluzione...Consigli ?? Indizi ? C'è qualche struttura dati che si possa usare? Grazie mille a tutti
banryu79
16-02-2009, 16:35
Salve ragazzi sto studiando Algoritmi e strutture dati e mi sono imbattuto in questo problema.
Descrivere ed analizzare un algoritmo che, in tempo O(n log n), dato un insieme S di numeri interi e un altro intero x, determini se esistono due elementi in S la cuimedia aritmetica è esattamente x
Non tenendo conto del tempo di esecuzio è semplice trovare un algoritmo, bastano due cicli innestati e controllare le coppie a una a una...il problema è proprio il requisito relativo al tempo di esecuzione O (n log n). Ci sto pensando da due giorni ma non riesco a trovare una soluzione...Consigli ?? Indizi ? C'è qualche struttura dati che si possa usare? Grazie mille a tutti
Non vorrei dire una fesseria, anzi ricordare male, ma mi sembra che ci fosse stato un Context dove si toccava l'argomento? Se passa Vincenzo o Cionci magari ti sanno dire meglio, visto che hanno sempre partecipato ai Context... potresti trovare dei buoni spunti :)
Pensa che due A e B hanno media X solo se (X - A) = -(X -B)...e pensa che ci sono alcuni algoritmi di ordinamento molto efficienti ;)
qwerty86
16-02-2009, 16:43
Ero arrivato a dover ordinare l'array e di quelli efficienti so che impiegano un tempo O(n log n)....giusto ? Io avevo pensato che A +B = x*2...ma veramente sono bloccato...:muro:
Ordinali per |X - V(i)|...cioè accompagna ai valori anche un altro vettore con la differenza da X ed ordinali per il valore assoluto.
qwerty86
16-02-2009, 17:02
Ordinali per |X - V(i)|...cioè accompagna ai valori anche un altro vettore con la differenza da X ed ordinali per il valore assoluto.
Ok ho capito che i due elementi che hanno lo stesso valora assoluto sono i due elementi che sto cercando ma come faccio a fare ciò in tempo O(n log n) ??
Non è che ti posso dire tutto :D
Come sai ci sono algoritmi di ordinamento O(n log n)...
Differenza e costruzione del vettore: O(n)
Ordinamento per il valore assoluto: O(n log n)
Ricerca elementi consecutivi con lo stesso valore assoluto e segno opposto: O(n)
O(n log n) è predominante ;)
qwerty86
16-02-2009, 17:10
Non è che ti posso dire tutto :D
Come sai ci sono algoritmi di ordinamento O(n log n)...
Differenza e costruzione del vettore: O(n)
Ordinamento per il valore assoluto: O(n log n)
Ricerca elementi consecutivi con lo stesso valore assoluto e segno opposto: O(n)
O(n log n) è predominante ;)
Grazie mille :)
rеpne scasb
16-02-2009, 20:30
■
qwerty86
16-02-2009, 20:32
Si risolve senza ordinare nulla in O(n).
Come??? :confused:
rеpne scasb
16-02-2009, 20:43
■
wingman87
16-02-2009, 22:16
Potresti spiegarlo a parole? Grazie
Edit: Ho capito, lo shift mi aveva mandato in confusione ma bastava vederlo come un *2.
repne...è normale che si risolva in O(n) così...hai fatto un ordinamento in O(n) ;)
I limiti di questa soluzione sono nell'uso della memoria: metti MAX_NUMBERS a 2^32 ;)
Edit: inoltre in due casi ci possono essere buffer overflow: se X è più grande di MAX_NUMBERS e se S contiene numeri negativi.
Quindi non è una soluzione valida in generale, ma valida solo in presenza di determinati vincoli.
rеpne scasb
17-02-2009, 08:41
■
qwerty86
17-02-2009, 08:43
Penso che la soluzione ci Cionci era quella chiesta nella traccia...Ne avrei un' altra che credo di aver risolto. Ecco :
Descrivere ed analizzare un algoritmo che, in tempo O(log n), dato un vettore ordinato A[1:::n] di interi distinti, determini se esiste o meno un intero i tale che A[i] = i.
La mia soluzione :
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a[4];
a[0]=-1;
a[1]=0;
a[2]=1;
a[3]=3;
if(ricerca_binaria(a,0,4) == 1)
printf("trovatooooo\n");
else
printf("non trovatoooooo\n");
}
int ricerca_binaria(int array[],int start, int end)
{
int m;
while(end >= start)
{
m= ((start + end)/2);
if(m == array[m]) return 1;
if (m < array[m])
end=(m-1);
else
start= (m+1);
ricerca_binaria(array,start,end);
}
return (0);
}
In pratica uso la ricerca binaria.Invece di confrontare il numero da ricercare con il valore centrale confronto quest'ultimo proprio con l'indice centrale . Sembra funzionare...:)
rеpne scasb
17-02-2009, 08:47
■
Ti assicuro che se metto MAX_NUMBER pari a 2^32 (in questo caso uso dei char), non emette lamento. Si puo' anche aggiungere che potrei utilizzare 1 solo bit in questo caso mi servono solo 512MiB di RAM (e funzionerebbe anche nello spazio d'indirizzamento di una CPU a 32-bit).
Ok, ma non è una soluzione sempre applicabile o comunque sempre conveniente. Stai sicura che pur essendo O(n) se scelgo dei numeri ad hoc fa prima una soluzione O(n log n) ;) Basta che si metta a swappare.
Tra l'altro se dovessi usare l'allocazione dinamica (basta che i numeri vengano immessi da tastiera e si è obbligati ad usarla) nel tempo in cui allochi il vettore, l'altro ha già finito ;)
Naaa...Non mi puoi cadere su una cosa del genere! Modificare il codice e' talmente semplice che neanche ci provo. :D
Sulla X, d'accordo, basta impostare la dimensione del vettore a max(X, max(S[i])), ma sui numeri negativi dovresti impostare la dimensione del vettore alla differenza fra X/2 - min(S[i])...ed a quel punto usare un displacement nel vettore...cosa che porterebbe ad ampliare ulteriormente il vettore.
In ogni caso utilizzare quell'algoritmo di "ordinamento" è una scelta oculata solo nel caso in cui si debbano ordinare N numeri di cui sappiamo a priori che la differenza fra il max e il min è minore di un certo K...con K << della quantità di ram del PC ;) Indicativamente conviene fino a quando lo stack riesce a contenere K.
E no, questa non te la lascio passare (l'ho notata solo ad una seconda rilettura).
Tu sostieni che ho fatto un ordinamento O(n). Ok. Allora se ho ordinato S dopo il codice:
for(i = 0; i < MAX_NUMBERS; ++i)
{
if(bitmap[i] != 0)
printf("%d\n", i);
}
Ovviamente l'ordinamento si ferma quando l'algoritmo trova gli elementi che hanno la media cercata, la stessa cosa sarebbe anche stata applicabile ad un qualsiasi altro algoritmo di ordinamento controllando gli elementi vicini al momento del posizionamento di un nuovo elemento.
In pratica uso la ricerca binaria.Invece di confrontare il numero da ricercare con il valore centrale confronto quest'ultimo proprio con l'indice centrale . Sembra funzionare...:)
E' O(n log n), funziona ==> va bene ;)
qwerty86
17-02-2009, 09:16
E' O(n log n), funziona ==> va bene ;)
La ricerca binaria non è O(logn) :D
La ricerca binaria non è O(logn) :D
Mi ci è rimasto un n in più ;)
qwerty86
17-02-2009, 09:27
Mi ci è rimasto un n in più ;)
Grazie....Speriamo vada bene quest'esame!
rеpne scasb
17-02-2009, 09:46
■
Lo so che si può fare, ma non ha senso. Metti che gli interi da valutare siano 10...che senso ha allocare 512 MB ? :D
rеpne scasb
17-02-2009, 09:54
■
E' per una buona causa, concedetemi il link: http://www.trovaprezzi.it/prezzo_memorie_512_mb.aspx :p :p :p
Che c'entra ? Allocare ram nello heap, per giunta azzerandola, ha un costo di tempo sia pratico che teorico.
Dovendo azzerare tutti gli elementi il tuo algoritmo, anche quello precedente, è O(n), ma con n pari a MAX_NUMBER ed in questo caso a 2^29 e non O(m) con m pari al numero di elementi in S.
Quindi teoricamente il tuo algoritmo non conviene fino a quando m log(m) >= n
rеpne scasb
17-02-2009, 10:04
■
Stai confrontando pere con banane. Pensaci.
No, è perfettamente corretto. E si vede anche nel tuo primo codice.
for(i=0;i<MAX_NUMBERS;i++)
bitmap[i]=0;
La grandezza predominante è MAX_NUMBERS e non N. Di conseguenza il tuo algoritmo è O(MAX_NUMBERS) e non O(N).
Quindi rispetto ad un algoritmo O(N log N) il tuo algoritmo permette, dal punto di vista teorico, di superare l'altro solo al crescere di N, ed in particolare quando N log N supera MAX_NUMBERS.
L'algoritmo di Repne si puo' risolvere senza allocare un array cosi' grande, facendo uso di HashTable, restando in O(N) se non sbaglio.
Cosi' avevo risolto un contest simile a questo (Trovare se esistono 2 valori che sommati fra loro diano X), e i risultati erano buoni, se ricordo bene.
L'algoritmo di Repne si puo' risolvere senza allocare un array cosi' grande, facendo uso di HashTable, restando in O(N) se non sbaglio.
Sì...chiaramente con un hash table funziona meglio, ma anche lì è O(N) con N uguale al numero di elementi nella struttura base dell'hash table (che va comunque inizializzata).
Sì...chiaramente con un hash table funziona meglio, ma anche lì è O(N) con N uguale al numero di elementi nella struttura base dell'hash table (che va comunque inizializzata).
Dovrebbe essere O(N) con N pari al numero di elementi del vettore originale, non appena N inizia ad essere ragionevolmente grande.
Poi si puo' provare a vedere conti alla mano quanto e' questo N, ma ritengo che con le nostre macchine (e almeno con Java, C# e le Boost) sia abbastanza basso da poter sostenere che e' praticamente O(N) sempre.
Dovrebbe essere O(N) con N pari al numero di elementi del vettore originale, non appena N inizia ad essere ragionevolmente grande.
Se il numero degli elementi del vettore iniziale è superiore al numero degli elementi della struttura base dell'hash allora concordo. Bene o male è lo stesso discorso che facevo prima, la struttura di repne si comporta come un hash quando il numero di elementi del vettore tende a salire (non a caso la condizione che avevo imposto prima è verificata in questa situazione).
rеpne scasb
17-02-2009, 13:12
■
Nota che ho scritto...teoricamente ;) L'ho anche ripetuto due volte.
Infatti mi riferivo alla teoria della complessità in cui la complessità di un algoritmo si misura a meno di costanti moltiplicative e additive e di componenti di ordine minore. Quella disequazione costituiva solo un fattore di merito. Andava letta come: fino a quando quelle due grandezze non sono comparabili il tempo di esecuzione del primo algoritmo è molto minore del secondo.
In ogni caso non fai altro che darmi ragione ;)
PS: sul logaritmo il tuo calcolo è sbagliato perché il logaritmo deve essere in base 2, non il logaritmo naturale. Quindi manca anche una costante moltiplicativa di 1/ln(2)
rеpne scasb
17-02-2009, 16:41
■
E' chiaro che 1/ln(2) sta dentro a3.
In effetti :doh:
Cosa vuoi che ti dica?
Ammettere per una volta che ti sei sbagliata non sarebbe male :D
cionci e rep... siete squisiti...
vi leggo sempre con molto piacere... eccellente...;)
per i newb... fatene tesoro....
rеpne scasb
20-02-2009, 10:15
■
wingman87
20-02-2009, 14:45
Supponendo a3 = q*a2 e a2 = q*a1 e posto k=a3 e m=MAX_NUMBER, si ha:
Non ho capito con quale logica hai supposto queste equivalenze, potresti spiegare per favore?
rеpne scasb
20-02-2009, 16:48
■
wingman87
20-02-2009, 17:57
q e' il rapporto tra a3 e a2 che per semplificazione l'ho supposto uguale a quello esistente tra a2 e a1. a1 a2 e a3 sono il peso rispetto tempo per n (a3,a2) e m (a1). Per quanto riguarda k e m non comprendo cosa ci sia da spiegare e' come se avessi scritto 18*2=36 e mi stessi chiedendo spiegazioni sul perche' 18 per 2 fa 36.
Infatti quello che non capivo era la prima parte, e a dire la verità ancora adesso non mi sembra corretto. Parlo di porre q=a3/a2 e al contempo anche q=a2/a1, questo si può avere solo con certe triple di a1,a2,a3 e in questo caso non mi sembra verosimile... boh, comunque ne sai certo più tu di me, se mi dici che è così mi fido. ;)
rеpne scasb
20-02-2009, 21:32
■
a3*n*ln(n)<a1*MAX_NUMBER + a2 * n
e non con quell'obbrobrio che hai scritto tu:
m log(m) >= n
Adesso e' chiaro? Non puoi comparare il peso di n rispetto a MAX_NUMBERS prendendoli come valori assoluti, prescindendo dalle costanti moltiplicativi a1, a2 e a3. Se confronti n e MAX_NUMBERS a meno di a1, a2 e a3 confronti le pere con le banane.
cionci è partito da un'ipotesi quasi sempre verificata, cioè che m<<n (n<<MAX_NUMBER, secondo la tua nomenclatura), perché i valori rappresentabili sono 2^32 (e determinano la dimensione della bitmap), mentre la cardinalità degli array da dare in pasto alle funzioni difficilmente supera qualche migliaio.
in tali e consuete situazioni, sempre secondo la tua nomenclatura:
MAX_NUMBER + a * n = O(MAX_NUMBER)
e la tua disequazione
a3*n*ln(n) < a1*MAX_NUMBER + a2 * n
diventa
O(nlogn) < O(MAX_NUMBER)
che è coerente con quella scritta, in maniera informale, da cionci.
che è coerente con quella scritta, in maniera informale, da cionci.
Che poi è quello che volevo dire...l'ho anche scritto a parole :boh:
rеpne scasb
21-02-2009, 12:42
■
if((bitmap=calloc(1<<((sizeof(long)<<3)-3),1))==NULL)
k=(x<<1)-j;
a1=((unsigned)(j+2147483648))>>3;
b1=((unsigned)(k+2147483648))>>3;
a2=1<<(j&0x07);
b2=1<<(k&0x07);
OT ma... volevo chiedere come mai usi sempre shifts anche per le cose più semplici, addirittura per sostituire una costante (512).
Oltre a rendere il codice abbastanza incomprensibile, siamo sicuri che su architetture moderne sia minimamente vantaggioso? :stordita:
Le moderne unità vettoriali (GPU) manco li supportano, per esempio.
rеpne scasb
21-02-2009, 16:12
■
Ma dici sul serio? :stordita:
rеpne scasb
21-02-2009, 17:43
■
cdimauro
21-02-2009, 18:57
OT ma... volevo chiedere come mai usi sempre shifts anche per le cose più semplici, addirittura per sostituire una costante (512).
Oltre a rendere il codice abbastanza incomprensibile, siamo sicuri che su architetture moderne sia minimamente vantaggioso? :stordita:
Le moderne unità vettoriali (GPU) manco li supportano, per esempio.
C'è di peggio: http://en.wikipedia.org/wiki/International_Obfuscated_C_Code_Contest :D
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.