[Generico] Algoritmo

[DanieleC88]

Salve, sto provando a risolvere questo esercizio:

Progettare un algoritmo con tempo di esecuzione O(n log n) che, dato in input un vettore T contenente n interi (con n > 0), conti il numeri di indici i n tali che il numero di elementi in T strettamente minore di T[i] è esattamente uguale ad i. T può contenere elementi ripetuti.

Per risolverlo, ho pensato a questo algoritmo:

algoritmo Conta(T)
{
    S = Sorted(T)

    i = 0
    count = 0

    while (i < Length[T])
    {
        j = BinarySearch(S, T[i])

        if (i = j - 1)
        {
            count += 1
        }

        i += 1
    }

    return count
}

Il mio ragionamento è il seguente: se effettuo una copia S dell'array (O(n)) ed un ordinamento della copia (O(n*log(n))), allora per ogni elemento dell'array posso fare una ricerca binaria nell'array ordinato (n * O(log(n)) = O(n*log(n))) e calcolare l'indice j in cui T[i] compare in S (e cioè per cui S[j] = T[i]). A questo punto, siccome S è ordinato, alla sua sinistra ci sono j - 1 elementi strettamente minori di T[i], per cui basta controllare che sia i = j - 1 ed incrementare il conteggio in corrispondenza.

Il problema viene quando l'array originale contiene elementi ripetuti. Ad esempio, un'array simile:

T = [4; 5; 3; 4; 2; 0; 1]

Ordinato, diventerebbe:

S = [0; 1; 2; 3; 4; 4; 5]

Il problema è che se viene selezionato il secondo dei due 4, il conteggio mi riporterà un numero in più del dovuto (alla sua sinistra c'è anche il primo dei 4, non solo i numeri ad esso minori). Ho pensato a tornare indietro fino alla prima posizione utile precedente a j, ma credo che alzi la complessità asintotica nel caso peggiore, se non sbaglio. Eliminare le ripetizioni, invece, darebbe risultati inesatti per i numeri più grandi (e quindi più a destra nell'array ordinato).

Qualcuno ha migliori idee?
ciao

[wingman87]

Potresti cercare invece del valore stesso il suo precedente (tanto sono interi) e poi usare, invece del solito BinarySearch, quello che se l'elemento non è presente restituisce la posizione in cui andrebbe inserito.
Comunque hai dimenticato di incrementare i nel ciclo.

Edit: cazzata, se il valore precedente è ripetuto sei punto e a capo. Continuo a rifletterci comunque, sembra interessante

Edit2: forse ho trovato! E se il BinarySearch non si fermasse quando trova l'elemento ma solo quando la porzione esaminata è un solo elemento? Così potresti pilotare la ricerca sull'elemento più a destra (se usi la mia soluzione) oppure più a sinistra se usi la tua. Così l'algoritmo di ricerca non è più log(n) solo nel caso peggiore ma in tutti i casi ma a te questo non importa.

[DanieleC88]

Originariamente inviato da wingman87

Comunque hai dimenticato di incrementare i nel ciclo.

Ops, vero, correggo (inizialmente era un "per ogni i in 1..n", poi ho modificato al volo).

Originariamente inviato da wingman87

Edit: cazzata, se il valore precedente è ripetuto sei punto e a capo. Continuo a rifletterci comunque, sembra interessante

Sì, e comunque non posso conoscere a priori il valore precedente, sempre ammesso che esista.

Originariamente inviato da wingman87

Edit2: forse ho trovato! E se il BinarySearch non si fermasse quando trova l'elemento ma solo quando la porzione esaminata è un solo elemento? Così potresti pilotare la ricerca sull'elemento più a destra (se usi la mia soluzione) oppure più a sinistra se usi la tua. Così l'algoritmo di ricerca non è più log(n) solo nel caso peggiore ma in tutti i casi ma a te questo non importa.

Hmm, non sono sicuro di aver capito bene in che modo intendi. Una volta trovato il numero esatto, secondo quale criterio dovrei continuare la ricerca? Diciamo che, oltre una comune ricerca binaria, dovrei poi scartare gli elementi uguali andando verso sinistra o verso destra? Mi resta il dubbio sulla complessità asintotica e sulla corrispondenza degli indici. Ma magari ho solo capito male!

Intanto grazie mille della risposta: spesso quando posto dubbi amletici come questo passo piuttosto inosservata, quindi grazie già per aver impegnato il tuo tempo a rispondermi.
ciao

[wingman87]

Allora, quello che intendo è questo:
la ricerca binaria in genere esamina una porzione di array, controlla l'elemento centrale e poi ci sono 3 casi:
1) se l'elemento è quello cercato hai finito
2) se è minore esamini la mezza porzione destra
3) se è maggiore esamini la mezza porzione sinistra
Io dicevo di modificare il punto 1 nel seguente modo, tenendo buona la tua soluzione di cercare l'elemento stesso:
1) se l'elemento è quello cercato esamino la mezza porzione sinistra compreso l'elemento stesso.
Bisogna solo fare attenzione nella condizione di terminazione.
Il risultato alla fine dovrebbe essere la posizione dell'elemento più a sinistra.

[DanieleC88]

Ok, ho capito, e penso che possa funzionare, rispettando anche il tempo O(log(n))... In fondo mi interessava più che altro la correttezza dell'algoritmo, e credo che ci sia. Se ti vengono in mente altre strade fammi sapere.

ciao e ancora grazie

[cionci]

Secondo me sta tutto nell'ordinamento...se fai un ordinamento in O(n log n) sei a posto.
Mi spiego meglio:

Dato T:
T = [4; 6; 3; 4; 2; 0; 1; 6]

Il vettore ordinato è:

S = [0; 1; 2; 3; 4; 4; 6; 6]

Ti scorri il vettore e nel farlo tieni conto dell'indice del primo elemento uguale all'elemento corrente. Dovrebbe bastare un semplice

index = (S[i] == S[index]) ? index : i;

Userai questo indice per vedere se la condizione è verificata. A questo punto la soluzione è banale.

[DanieleC88]

Infatti, se noti, è ciò che avevo proposto inizialmente: il problema è esattamente quello di trovare il primo numero nell'array ordinato che sia uguale al numero cercato. Una ricerca lineare darebbe un costo O(n^2), una ricerca binaria invece darebbe un costo O(n*log(n)), ma restava il problema di assicurarsi che l'elemento trovato fosse il primo utile senza alzare la complessità.

ciao

[wingman87]

Non sono sicuro che quello che sto per dire sia la stessa cosa che ha detto cionci perché non sono sicuro di aver capito ma leggendo il suo post mi è venuta in mente questa cosa, riprendendo l'esempio di cionci abbiamo:

Dato T:
T = [4; 6; 3; 4; 2; 0; 1; 6]

Il vettore ordinato è:
S = [0; 1; 2; 3; 4; 4; 6; 6]

ora scorri il vettore T e per ogni elemento T[i] se

S[i]==T[i] && ( i==0 || S[i-1]!=T[i])

incrementi il contatore.

[DanieleC88]

Hai ragione, credo che questa cosa possa funzionare, domani provo a dimostrarlo in qualche modo. Adesso non sono in grado di formulare molto ragionamenti arguti vista l'ora.

ciao

[cionci]

Originariamente inviato da DanieleC88

Infatti, se noti, è ciò che avevo proposto inizialmente: il problema è esattamente quello di trovare il primo numero nell'array ordinato che sia uguale al numero cercato. Una ricerca lineare darebbe un costo O(n^2), una ricerca binaria invece darebbe un costo O(n*log(n)), ma restava il problema di assicurarsi che l'elemento trovato fosse il primo utile senza alzare la complessità.

ciao

Non devi fare alcuna ricerca

E' lineare in O(n) perché, una volta ordinato, devi scorrere una sola volta il vettore.

index = 0;
count = 0;
for(i = 0; i < n; i++)
{
  index = (S[i] == S[index]) ? index : i;
  if(verifica la condizione usando index)
     count++;
}

index ad ogni iterazione contiene l'indice del primo numero incontrato uguale al numero corrente.

[DanieleC88]

Hmm, mi sa allora che avevo letto male il tuo vecchio post. Be' essenzialmente il funzionamento è lo stesso di quello proposto ieri da wingman87, che nel frattempo ho dimostrato essere corretto.

Vi ringrazio ancora!
ciao