DOMANDA Complessita' asintotica ricerca dicotomica

[MPG]

Scusate in classe (sono alle superiori) il prof ha spiegato questo in merito alla complessità asintotica :

Ricerca lineare: ricerca "classica" di un elemento in un vettore;
Ricerca dicotomica: parto da un array ordinato e procedo come spiegato( O(log2(n)). Notazioni O, Omega, Theta.

Qualcuno di buon cuore puo' aiutarmi a capire la ricerca dicotomica?
Grazie a tutti.

 

[Blume.]

Forse...
@Andretti60 oppure il professore @gronag

 

[fabio93]

La ricerca dicotomica o binaria prevede che l'array sia ordinato. Al primo tentativo, si controlla l'elemento centrale del vettore. Se è uguale a quello cercato, hai finito. Altrimenti, si ripete il procedimento nella metà di array (sottoarray) minore o maggiore rispetto all'elemento centrale, a seconda che questo sia risultato minore o maggiore di quello da cercare. Puoi immaginare il procedimento come se prendessi un segmento, individuassi il suo punto medio, e poi ripetessi l'operazione nel sottosegmento a sinistra o a destra del punto medio, e così via.
I simboli O (Omicron o "o grande"), Omega e Theta indicano rispettivamente un limite superiore, inferiore e sia superiore che inferiore alla crescita di una funzione, quindi alla complessità computazionale. Ad esempio se la complessità di un algoritmo è O(n), vuol dire che, alla peggio, avrà una complessità lineare.
Nel caso della ricerca dicotomica, la complessità nel caso pessimo è O(log2(n)) perché, dato un vettore di n elementi, tu controlli di volta in volta l'elemento centrale del sottoarray considerato, quindi dividi n per 2. Il logaritmo in base 2 di n ti dice il numero di volte che n deve essere diviso per 2 per arrivare a 1. Questo corrisponde al caso pessimo, quando in sostanza controlli l'elemento centrale del sottoarray più piccolo. Nel caso ottimo invece la complessità è O(1) perché lo becchi al primo colpo.

 

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

 

[MPG]

Per la ricerca binaria avrei trovato questo codice:

#include <iostream>
using namespace std;

#define x 15
#define N 5

int main(){
    int a[N]={1,5,8,10,15};
    int i=0, j=N-1, m, pos=-1;

    do { 
        m=(i+j)/2;
        if(a[m]==x)  
            pos=i;
        else if (a[i]<x)
            i=m+1;
        else
            j=m-1;
    } while(i<=j && pos==-1);    

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

Pero' non riesco bene a capirlo, inoltre non ho mai usato
#define

MI potete postare un code alternativo che faccia la ricerca binaria?

 

[BrutPitt]

Per la ricerca binaria avrei trovato questo codice:

#include <iostream>
using namespace std;

#define x 15
#define N 5

int main(){
    int a[N]={1,5,8,10,15};
    int i=0, j=N-1, m, pos=-1;

    do {
        m=(i+j)/2;
        if(a[m]==x) 
            pos=i;
        else if (a[i]<x)
            i=m+1;
        else
            j=m-1;
    } while(i<=j && pos==-1);   

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

Pero' non riesco bene a capirlo, inoltre non ho mai usato
#define

MI potete postare un code alternativo che faccia la ricerca binaria?

Lo hai compilato o hai compilato qualche esempio?
Hai provato a modificarne qualcuno per vedere cosa succede cambiando i parametri?

Credo che manchi un po' di buona volonta' nel capire cosa fa il codice, visto che ne avevamo anche parlato in privato e ti avevo indirizzato proprio a questo esempio (che e' anche commentato):

Ricerca binaria, algoritmo di ricerca binaria o dicotomica in C++

L’algoritmo di ricerca binaria o dicotomica è un algoritmo che viene utilizzato per trovare elementi in un array ordinato. Si usa il termine dicotomica

www.codingcreativo.it

Ti avevo anche indirizzato a quello in C contenuto in Wikipedia, ma soprattutto ci sono esempi, molto elementari, anche nelle dispense del professore che mi hai fatto vedere... capisco che son 30 pagine, ma lo studio gioverebbe allo scopo.
Oltretutto, come ti avevo anche gia' scritto, ci sono molti altri esempi in rete, anche in italiano (e' un algoritmo molto comune), ma non basta solo andarli a consultare, bisogna passare del tempo a comprenderli.

E bisogna anche imparare il linguaggio di programmazione andandosi a "guardare", per esempio, cosa fa il #define, che e' una semplicissima direttiva del preprocessore C/C++:

direttiva #define (C/C++)

Altre informazioni su: direttiva #define (C/C++)

docs.microsoft.com

che qui ti chiarisco in modo semplicistico, in questo caso:
#define N 5
associa ad N il numero 5, ossia dove c'e' N e' come se ci fosse 5
in questo caso (e solo in questo caso, non e' da generalizzare!) e' come se scrivessi:
const int N = 5;

Se poi hai dei dubbi su qualche passaggio particolare (e non su tutto il codice, perche' altrimenti sembra che tu non l'abbia nemmeno guardato), saro'/saremo lieti di aiutarti.

 

[Andretti60]

Scusa ma non si capisce bene cosa stai chiedendo in quanto parli di due concetti

1. complessita' computazionale.
2. ricerca per dicotomia.

Sono due cose diverse.

Il primo e' un concetto puramente teorico che esprime quanto complesso dal punto di vista temporale (ossia tempo di esecuzione) sia un algoritmo. E ci sarebbe da scrivere a fiumi, infatti e' uno dei fondamenti dell'informatica. Se non lo capisci e' inutile che vai avanti negli studi.

Il secondo e' semplicemente un algoritmo di ricerca, ottimizzato rispetto alla ricerca lineare. E' uno degli algoritmi classici che vengono usati per descrivere come un algoritmo di complessita' O(n) possa essere ridotto a complessita' O(log(n)).

PS il codice da te postato non funziona, c'e' un indice sbagliato.

PPS ho scritto una guida su come dare i nomi alle variabili, sembra una cosa stupida ma guarda cosa significa chiamare le variabili semplicemente con una lettera i, j , m, k. Non si capisce nulla, Se le avessero chiamate con nomi piu' rappresentativi, il codice sarebbe enormemente piu' facile da capire. E quelle sono solo poche linee (che uno con esperienza capisce subito) immaginate cosa succede quando ci si trova un programma di centinaia di linee dove ogni variabile e' chiamata i. Non smettero' mai di ribadire questo concetto.

 

[pabloski]

else if (a[i]<x)

dev'essere

else if (a[m]<x)

per il resto è un codice molto semplice

1. prende il vettore a e si piazza giusto in mezzo ( m )
2. se a[m] è più piccolo di x, allora ( siccome il vettore è ordinato ) x si trova sicuramente nella metà destra di a
3. in caso contrario, si trova nella metà sinistra
4. se a[m] == x, ovviamente l'hai trovato

e chiaramente termina se l'ha trovato ( pos != -1 ) o è arrivato a scansionare tutto il vettore senza trovare x ( i == j )

un'altra implementazione è quella ricorsiva ( da cui è più facile visualizzare la complessità computazionale ), ma temo ti creerebbe altra confusione

 

[MPG]

Dunque io ho provato cosi' cercando ci capire:

#include <iostream>
using namespace std;




int main()
{   int N=5;
    int numeri[N]={1,3,4,7,10};
    for (int i=0;i<N;i++)
    {
        cout<<numeri[i]<<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;
}

Non capisco dove sbaglio....

 

[Andretti60]

Riguardo al #define, le istruzioni che iniziano con il cancelletto sono "direttive del precompilatore", che e' il passo precedente al compilatore stesso, ed e' una caratteristica del linguaggio C, poi importata nel linguaggio C++ ma adesso deprecata. E' un linguaggio vero e proprio, se fai un uso pesante del linguaggio C, lo devi studiare.

Post unito automaticamente: 18 Febbraio 2020

...
Non capisco dove sbaglio....

Guarda la linea:

while (trovato=false  &&   (indiceLimiteSinistro <= indiceLimiteDestro));

 

[MPG]

Caspita non riesco a sistemare:

while (trovato=false && (indiceLimiteSinistro <= indiceLimiteDestro));

Non riesco a capire cosa sbaglio veramente, sarà una cavolata ma non mi viene.....

 

[Andretti60]

trovato=false

Post unito automaticamente: 18 Febbraio 2020

Non so che compilatore usi, ma quel codice con qualsiasi compilatore ANSI C ti spara un avvertimento grande come una casa.

 

[MPG]

trovato=false

Post unito automaticamente: 18 Febbraio 2020

Non so che compilatore usi, ma quel codice con qualsiasi compilatore ANSI C ti spara un avvertimento grande come una casa.

Uso codeblocks e non mi viene nulla come errore....

 

[Andretti60]

L'istruzione while prevede di avere al suo interno un test condizionale.
Quello che hai scritto e' una assegnazione.
Di piu', mi spiace, dirti non posso o giovane padawan.

 

[MPG]

trovato==false......
Immaginavo che era una cavolata... ma fondamentale.

Post unito automaticamente: 18 Febbraio 2020

Lo hai compilato o hai compilato qualche esempio?
Hai provato a modificarne qualcuno per vedere cosa succede cambiando i parametri?

Credo che manchi un po' di buona volonta' nel capire cosa fa il codice, visto che ne avevamo anche parlato in privato e ti avevo indirizzato proprio a questo esempio (che e' anche commentato):

Ricerca binaria, algoritmo di ricerca binaria o dicotomica in C++

L’algoritmo di ricerca binaria o dicotomica è un algoritmo che viene utilizzato per trovare elementi in un array ordinato. Si usa il termine dicotomica

www.codingcreativo.it

Ti avevo anche indirizzato a quello in C contenuto in Wikipedia, ma soprattutto ci sono esempi, molto elementari, anche nelle dispense del professore che mi hai fatto vedere... capisco che son 30 pagine, ma lo studio gioverebbe allo scopo.
Oltretutto, come ti avevo anche gia' scritto, ci sono molti altri esempi in rete, anche in italiano (e' un algoritmo molto comune), ma non basta solo andarli a consultare, bisogna passare del tempo a comprenderli.

E bisogna anche imparare il linguaggio di programmazione andandosi a "guardare", per esempio, cosa fa il #define, che e' una semplicissima direttiva del preprocessore C/C++:

direttiva #define (C/C++)

Altre informazioni su: direttiva #define (C/C++)

docs.microsoft.com

che qui ti chiarisco in modo semplicistico, in questo caso:
#define N 5
associa ad N il numero 5, ossia dove c'e' N e' come se ci fosse 5
in questo caso (e solo in questo caso, non e' da generalizzare!) e' come se scrivessi:
const int N = 5;

Se poi hai dei dubbi su qualche passaggio particolare (e non su tutto il codice, perche' altrimenti sembra che tu non l'abbia nemmeno guardato), saro'/saremo lieti di aiutarti.

Il concetto l'ho capito pero' vorrei capire meglio quel pos=-1 qui.
Cioè "pos" rappresenterebbe la posizione nell'array del numero trovato ma non capisco l'impostazione pos=-1.

#include <iostream>
using namespace std;

#define x 15
#define N 5

int main(){
    int a[N]={1,5,8,10,15};
    int i=0, j=N-1, m, pos=-1;    ////??????

    do {
        m=(i+j)/2;
        if(a[m]==x)
            pos=i;
        else if (a[m]<x)
            i=m+1;
        else
            j=m-1;
    } while(i<=j && pos==-1);     ////?????

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

    return 0;
}