DOMANDA Complessita' asintotica ricerca dicotomica

[Andretti60]

... Il concetto l'ho capito pero' vorrei capire meglio quel pos=-1

in quel codice la variabile pos e' usata per "segnalare" l'indice del vettore che corrisponde al numero da trovare. E' uno "sporco" trucco usato molto in programmazione. Il metodo classico, elegante e a prova di errore, e' di usare una variabile booleana, che viene inizializzata con False e poi cambiata a True quando il valore e' stato trovato (come nel tuo ultimo esempio). Quando si sa "a priori" che un particolare valore di una variabile e' illegale, si evita di usare una seconda variabile booleana. In quel caso pos indica l'indice di un vettore, quindi un valore "legale" dovra' essere maggiore o uguale a zero (ossia l'indice di un vettore), quindi viene inizializzata con un valore negativo (-1 in questo caso), e finche' il suo valore rimane negativo significa che l'algoritmo non ha trovato l'elemento che si cerca.

E' una tecnica molto comune, specie in Standard C (che non ha il tipo Boolean). Anche io la uso spesso (anche in altri linguaggi), ma occorre stare attenti. Puo' funzionare all'inizio, poi magari si modifica il codice, se succede che l'intervallo del valori accettabili cambia il codice non funziona piu'. Della serie "usa a tuo rischio e pericolo" :) Una situazione sicura e' quando si cerca un puntatore, in quel caso si e' sicuri che il valore null (zero) sara' sempre illegale.

 

[MPG]

Grazie, non capivo assolutamente, ma quindi "pos" è piu' usato nel C che in C++?
Ritieni piu' "corretto" il secondo code con bool che ho scritto quindi?
E' corretto dire che pos=-1 è la posizione dell’elemento da cercare e -1 significa NON trovato ?

 

[rodhellas]

Grazie, non capivo assolutamente, ma quindi "pos" è piu' usato nel C che in C++?

E' una tecnica molto comune, specie in Standard C (che non ha il tipo Boolean). cit. @Andretti60

Ritieni piu' "corretto" il secondo code con bool che ho scritto quindi?

Il metodo classico, elegante e a prova di errore, e' di usare una variabile booleana, che viene inizializzata con False e poi cambiata a True quando il valore e' stato trovato (come nel tuo ultimo esempio). cit @Andretti60

E' corretto dire che pos=-1 è la posizione dell’elemento da cercare e -1 significa NON trovato ?

In quel caso pos indica l'indice di un vettore, quindi un valore "legale" dovra' essere maggiore o uguale a zero (ossia l'indice di un vettore), quindi viene inizializzata con un valore negativo (-1 in questo caso), e finche' il suo valore rimane negativo significa che l'algoritmo non ha trovato l'elemento che si cerca. @Andretti60

 

[pabloski]

E' corretto dire che pos=-1 è la posizione dell’elemento da cercare e -1 significa NON trovato ?

Occhio. Non è che quello sia un concetto generale del C. E' il tuo programma che sfrutta quel trucco.

Infatti tu scrivi

int i=0, j=N-1, m, pos=-1;

Come vedi, pos viene settato a -1 prima di cominciare la ricerca. E che succede dopo?

if(a[m]==x) 
            pos=i;

Cioè, se trovi l'elemento che cercavi, pos diventa uguale alla posizione dell'elemento, altrimenti resta -1 anche dopo l'uscita dal ciclo do while.

Quindi non è che il C fa così. E' il tuo programma che fa così. Ovviamente funziona la cosa, per la successiva valutazione che il programma fa, ovvero

 if(pos!=-1)
        cout<<"numero trovato in posizione: "<<pos<<endl;
    else 
        cout<<"numero non trovato";

 

[MPG]

L'analisi di complessita' e' detta asintotica se i il numero dei dati tende all'infinito.
La ricerca dicotomica e' una ricerca che opera all'interno di un array ordinato.
Si usa "dicotomica", perche' dal greco "dicotimia" e' letteralmente "taglio in due" ed infatti si opera tagliando progressivamente in due parti i gruppi di elementi da valutare.
Come si effettua:

1. Si compara l'elemento centrale del gruppo di elementi.
2. Se questi corrisponde all'elemento cercato la ricerca e' terminata --> fine della ricerca: elemento trovato
3. Se questi e' superiore, il risultato e' da ricercare solo negli elementi precedenti. (scarto la meta' successiva)
4. Se questi e' inferiore, il risultato e' da ricercare solo negli elementi successivi. (scarto la meta' precedente)
5. Il gruppo adesso e' diventato la meta' (tagliato in 2, in base alla selezione 3 o 4).
6. Se il nuovo gruppo di ricerca e' vuoto --> fine ricerca: elemento non trovato - altrimenti torno al punto 1.

O(log2(n)) e' il numero massimo di confronti che verranno effettuati per trovare o non trovare (verificare che non c'e') l'elemento, contrapposto a O(n) che e' il numero massimo di confronti da effettuare in una ricerca classica.

Per cio' che riguarda i termini:

• "n" e' il numero di elementi che compongono l'array (il campione dei dati).
• Il simbolo "O" equivale a <= (O(log2(n)) equivale a dire che verra' effettuato un numero di comparazioni <= log2(n), per trovare o verificare l'assenza dell'elmento)
• Il simbolo "o" equivale a <
• Il simbolo "Theta" equivale a == (uguale) - (T(log2(n)) equivale a dire che verranno fatte esattamente log2(n) iterazioni per dire che l'elemento non e' nel gruppo)
• Il simbolo "OMEGA" equivale a >=
• C'e' anche "omega" (minuscola) che equivale a >

SCusa hai scrittto:
"
O(log2(n)) e' il numero massimo di confronti che verranno effettuati per trovare o non trovare (verificare che non c'e') l'elemento, contrapposto a O(n) che e' il numero massimo di confronti da effettuare in una ricerca classica.
"
IN questo:

int main()
{   int N=5;
    int numeri[N]={1,3,4,7,10};
    for (int i=0;i<N;i++)
    {
        cout<<numeri<<endl;
    }

     int numeroCercato=7;
     int indiceLimiteSinistro=0;
     int indiceLimiteDestro= N-1;
     int indiceOsservato;
     bool trovato= false;
    do {
        indiceOsservato= (indiceLimiteSinistro+indiceLimiteDestro)/2;
        if(numeri[indiceOsservato] == numeroCercato)
        {
            trovato=true;
        }
        else

        {

         if(numeri[indiceOsservato] > numeroCercato)
    {

       indiceLimiteDestro=indiceOsservato-1;
    }

    else
    {

       indiceLimiteSinistro=indiceOsservato+1;
    }
    }
}

    while (trovato=false  &&   (indiceLimiteSinistro <= indiceLimiteDestro));
    if (trovato)
    {
        cout<<"Numero trovato alla posizione: "<<indiceOsservato;

    }
    else

    {
        cout<<"Numero non trovato alla posizione:" << indiceOsservato;
    }


    return 0;
}

il log2(n) e' quindi log2(5)?

INoltre guardavo qui alcune spiegazioeni sulle notificazioni O ,theta e omega, vedo mi pare specifiche diverse da quello che hai scritto:

• Il simbolo "Theta" equivale a == (uguale) - (T(log2(n)) equivale a dire che verranno fatte esattamente log2(n) iterazioni per dire che l'elemento non e' nel gruppo)
• Il simbolo "OMEGA" equivale a >=
• C'e' anche "omega" (minuscola) che equivale a >

La notazione asintotica

www.andreaminini.org

Nel senso che tu mi dici che sono simboli con un significato diciamo matematico mentre nell'altro link si parla di
confrontare il tasso di crescita ( comportamento asintotico ) di una funzione nei confronti di un'altra con queste notazioni.

 

[BrutPitt]

L'analisi di complessita' e' detta asintotica se i il numero dei dati tende all'infinito.
La ricerca dicotomica e' una ricerca che opera all'interno di un array ordinato.

Onestamente, parlando di ricerca dicotomica, in un forum di programmazione, mi sono riferito alla compessita' dell'algoritmo in questione, piu' che alla notazione asintotica in matematica e degli algoritmi in generale.
Poi con la mia esemplificazione cercavo di far comprendere, in termini pratici, a cosa facessero riferimento determinati simboli... come poterli associare "praticamente" ad un algoritmo (anzi, a quest'algoritmo in particolare)... anche perche' dal punto di vista teorico ci sono tante documentazioni fatte molto meglio di come potrei scriverela io.

Da dove deriva questa esemplificazione?

Detta T(n) la nostra ricerca dicotomica:

"O" definisce sempre il limite superiore della complessita' dell'algoritmo,... meglio: O(f(n)) definisce questo limite come funzione asintotica, con f(n) funzione maggiorante.
Dal punto di vista di calcolo di un algoritmo generale, "O" e' la stima per eccesso fatta di quell'algoritmo... (parliamo in termini di tempo)
Nel caso particolare, nella ricerca dicotomica, questo limite superiore e' appunto O(log2(n))... o meglio, dovendo parlare in termini di tempo: assegnato un tempo t=1s ad ogni comparazione (in modo semplicistico), il tempo di esecuzioine diventa log2(n)s, dove n e' il numero degli elementi.
In definitiva il numero di iterazioni (tempo di esecuzione) di T(n) non sara' mai superiore ad O(log2(n)) (dove log2(n) e' funzione maggiorante di T(n)), quindi scrivere O(log2(n)) equivale a dire che il tempo di calcolo dell'algoritmo dicotomico sara' sempre <= a log2(n)s, o se vuoi, il numero di iterazioni sara' sempre <= a log2(n).
O ancora scrivere T(n) = O(log2(n)) ... equivale a scrivere T(n) <= log2(n)
O in modo esaustivo e generale dire: "la complessita' di T(n) e' O(f(n))"... e' come dire: "il tempo di esecuzione di T(n) e' <= f(n)"
Da qui l'esemplificazione O equivale a <=


Analogo discorso per OMEGA, che definisce la stima per difetto dell'algoritmo.

Teta definisce un limite asintoittioco stretto... meglio: Teta(f(n)) definisce strettamente l'andamento dell'algoritmo T(n), con f(n) che cresce come T(n), incanalando T(n) tra due andamenti della funzione f(n): a*f(n) <= T(n) <= b*f(n) (a, b > 0)
Tralasciando tutti i passaggi fatti per "O", dire che "la complessita' di T(n) e' Teta(f(n))" equivale a dire che "il tempo di esecuzione di T(n) e' uguale a f(n)"
Passando alla nostra ricerca dicotomica T(n), nel caso in cui non vi siano mai occorrenze, scrivere T(n) = Teta(log2(n)) equivale a scrivere che T(n) == log2(n).

Per cio' che riguarda "o" e "omega" definiscono rispettivamente f(n) come funzione strettamente maggiorante, e funzione strettamente minorante di T(n).
Da qui l'esemplificazione descritta.

Mi preme aggiungere, per evitare fraintendimenti:
Queste esemplificazioni non devono mai essere utilizzate per sostutire la simbologia, e' solo un modo "pratico" per comprendere/ricordare un concetto.

P.S.
Il tempo, in un algoritmo, in realta' e' una somma pesata delle singole istruzioni.
In questo esempio, di ricerca dicotomica, ho esemplificato/sostituito il tempo di caclolo con il numero di iterazioni, in quanto il costo di una "comparazione" e' simile nell'andamento dell'algoritmo, cosi', per semplificare tutto, il tempo e' stato associato/sostituito al numero di comparazioni/iterazioni.

il log2(n) e' quindi log2(5)?

Si', ma essendo log2(n) un numero appartenete ad R, mentre il numero di iterazioni e' un numero appartenete a N, il numero di iterazioni dell'algoritmo deve essere approssimato per eccesso.
Per es. log2(5) = 2.3xxxx -> numero di MASSIMO di iterazioni = 3

Forse e' piu' corretto dire che il numero massimo di iterazioni e' floor(log2(n) + 1) ... usando una notazione C

 

[tom-BH]

Onestamente, parlando di ricerca dicotomica, in un forum di programmazione, mi sono riferito alla compessita' dell'algoritmo in questione, piu' che alla notazione asintotica in matematica e degli algoritmi in generale.
Poi con la mia esemplificazione cercavo di far comprendere, in termini pratici, a cosa facessero riferimento determinati simboli... come poterli associare "praticamente" ad un algoritmo (anzi, a quest'algoritmo in particolare)... anche perche' dal punto di vista teorico ci sono tante documentazioni fatte molto meglio di come potrei scriverela io.

Da dove deriva questa esemplificazione?

Detta T(n) la nostra ricerca dicotomica:

"O" definisce sempre il limite superiore della complessita' dell'algoritmo,... meglio: O(f(n)) definisce questo limite come funzione asintotica, con f(n) funzione maggiorante.
Dal punto di vista di calcolo di un algoritmo generale, "O" e' la stima per eccesso fatta di quell'algoritmo... (parliamo in termini di tempo)
Nel caso particolare, nella ricerca dicotomica, questo limite superiore e' appunto O(log2(n))... o meglio, dovendo parlare in termini di tempo: assegnato un tempo t=1s ad ogni comparazione (in modo semplicistico), il tempo di esecuzioine diventa log2(n)s, dove n e' il numero degli elementi.
In definitiva il numero di iterazioni (tempo di esecuzione) di T(n) non sara' mai superiore ad O(log2(n)) (dove log2(n) e' funzione maggiorante di T(n)), quindi scrivere O(log2(n)) equivale a dire che il tempo di calcolo dell'algoritmo dicotomico sara' sempre <= a log2(n)s, o se vuoi, il numero di iterazioni sara' sempre <= a log2(n).
O ancora scrivere T(n) = O(log2(n)) ... equivale a scrivere T(n) <= log2(n)
O in modo esaustivo e generale dire: "la complessita' di T(n) e' O(f(n))"... e' come dire: "il tempo di esecuzione di T(n) e' <= f(n)"
Da qui l'esemplificazione O equivale a <=


Analogo discorso per OMEGA, che definisce la stima per difetto dell'algoritmo.

Teta definisce un limite asintoittioco stretto... meglio: Teta(f(n)) definisce strettamente l'andamento dell'algoritmo T(n), con f(n) che cresce come T(n), incanalando T(n) tra due andamenti della funzione f(n): a*f(n) <= T(n) <= b*f(n) (a, b > 0)
Tralasciando tutti i passaggi fatti per "O", dire che "la complessita' di T(n) e' Teta(f(n))" equivale a dire che "il tempo di esecuzione di T(n) e' uguale a f(n)"
Passando alla nostra ricerca dicotomica T(n), nel caso in cui non vi siano mai occorrenze, scrivere T(n) = Teta(log2(n)) equivale a scrivere che T(n) == log2(n).

Per cio' che riguarda "o" e "omega" definiscono rispettivamente f(n) come funzione strettamente maggiorante, e funzione strettamente minorante di T(n).
Da qui l'esemplificazione descritta.

Mi preme aggiungere, per evitare fraintendimenti:
Queste esemplificazioni non devono mai essere utilizzate per sostutire la simbologia, e' solo un modo "pratico" per comprendere/ricordare un concetto.

P.S.
Il tempo, in un algoritmo, in realta' e' una somma pesata delle singole istruzioni.
In questo esempio, di ricerca dicotomica, ho esemplificato/sostituito il tempo di caclolo con il numero di iterazioni, in quanto il costo di una "comparazione" e' simile nell'andamento dell'algoritmo, cosi', per semplificare tutto, il tempo e' stato associato/sostituito al numero di comparazioni/iterazioni.


Si', ma essendo log2(n) un numero appartenete ad R, mentre il numero di iterazioni e' un numero appartenete a N, il numero di iterazioni dell'algoritmo deve essere approssimato per eccesso.
Per es. log2(5) = 2.3xxxx -> numero di MASSIMO di iterazioni = 3

Forse e' piu' corretto dire che il numero massimo di iterazioni e' floor(log2(n) + 1) ... usando una notazione C

Ciao, ho trovato molto interessante il tuo post e per tale motivazione ti vorrei sottoporre questa domanda(strettamente legata alla ricerca binaria): se ho capito bene quindi in teoria quando applico questo algoritmo a un vettore ordinato crescentemente il mio algoritmo farà al massimo (caso peggiore) log2(n); ma nel caso migliore (che so essere perfettamente trascurabile) il numero di iterazioni e O(1)?

 

[Edmund Blackadder]

ma nel caso migliore (che so essere perfettamente trascurabile) il numero di iterazioni e O(1)?

Il caso migliore è quando dividi a metà la sequenza per la prima volta e il numero che cerchi si trova proprio lì. Quindi fai solo un'operazione aritmetica e un confronto e quindi impieghi O(1).