Piccolo problema di algoritimi

[qwerty86]

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]

Originariamente inviato da qwerty86

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

[cionci]

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]

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...

[cionci]

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]

Originariamente inviato da cionci

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) ??

[cionci]

Non è che ti posso dire tutto
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]

Originariamente inviato da cionci

Non è che ti posso dire tutto
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]

■

[qwerty86]

Originariamente inviato da rеpne scasb

Si risolve senza ordinare nulla in O(n).

Come???

[rеpne scasb]

■

[wingman87]

Potresti spiegarlo a parole? Grazie

Edit: Ho capito, lo shift mi aveva mandato in confusione ma bastava vederlo come un *2.

[cionci]

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]

■

[qwerty86]

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]

■

[cionci]

Originariamente inviato da rеpne scasb

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

Originariamente inviato da rеpne scasb

Naaa...Non mi puoi cadere su una cosa del genere! Modificare il codice e' talmente semplice che neanche ci provo.

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.

[cionci]

Originariamente inviato da rеpne scasb

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.

[cionci]

Originariamente inviato da qwerty86

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]

Originariamente inviato da cionci

E' O(n log n), funziona ==> va bene

La ricerca binaria non è O(logn)