calcolo della complessità temporale

[ghiotto86]

ciao raga.
mi servirebbe calcolare la complessità temporale di un mio algoritmo; devo vedere se ha complessità minore della ricerca binaria che è Log(n).

come si fa??

[pietro84]

Originariamente inviato da ghiotto86

ciao raga.
mi servirebbe calcolare la complessità temporale di un mio algoritmo; devo vedere se ha complessità minore della ricerca binaria che è Log(n).

come si fa??

che tipo di algoritmo è?

[mpattera]

vedi il tempo impiegato dal tuo e da quello che prendi con riferimento...

[ghiotto86]

Originariamente inviato da mpattera

vedi il tempo impiegato dal tuo e da quello che prendi con riferimento...

va + veloce rispetto alla ricerca binaria ma siccome devo fa una documentazione esterna vorrei esplicare la sua complessità temporale in termini di simboli.

[ghiotto86]

Originariamente inviato da pietro84

che tipo di algoritmo è?

è un algoritmo che dato un vettore x e un vettore t deve trovare in che intervallo si trova l'i-esimo t in x.

[mpattera]

per quanto mi ricordi dalle superiori la complessità computazionale di un algoritmo si misura osservando come cresce il numero di passi (iterazioni) da fare al crescere lineare del numero di elementi da trattare...quindi 1 elemento->n1 passi, 100 elementi->n2 passi, 1000 elementi-> n3 passi...e vedi la proporzione (funzione) che c'è tra elementi (x) e passi (y).

[pietro84]

Originariamente inviato da ghiotto86

va + veloce rispetto alla ricerca binaria ma siccome devo fa una documentazione esterna vorrei esplicare la sua complessità temporale in termini di simboli.

devi calcolare la complessità del tuo algoritmo, se è minore di O(logn) hai dimostrato che il tuo algoritmo va più veloce della ricerca binaria. dov'è che trovi difficoltà?

[ghiotto86]

Originariamente inviato da pietro84

devi calcolare la complessità del tuo algoritmo, se è minore di O(logn) hai dimostrato che il tuo algoritmo va più veloce della ricerca binaria. dov'è che trovi difficoltà?

trovo difficoltà nel calcolare quello che c'è dento la O tipo la ricerca binaria ha compl. O (log(n)).
la mia??

[mpattera]

nel come calcolare la complex del suo algoritmo credo...

[ghiotto86]

Originariamente inviato da mpattera

nel come calcolare la complex del suo algoritmo credo...

esatto.
cioè di come ricavare la formula matematica.
come hai detto te ogni passo dell'algoritmo costa tempo e infatti

>> prova
Elapsed time is 0.000000 seconds.
15365

Elapsed time is 0.000000 seconds.
2122

il 1° è la ricerca binaria.
il 2° è la mia ricerca.

posto i due algoritmi

binaria

     passi=0;
        for h=1:n_t
     
          pos(h) = -1;
          p=1;
          u=n-1;        
          passi=passi+1;
          while (p<=u && pos(h)==-1)   
              passi=passi+1;
          half=round((p+u)/2);      
            if (x(half)==t(h))
               pos(h)=half;
               passi=passi+1;
            else
              if (x(half)<t(h))
                  p=half+1;
                  passi=passi+1;
              else
                  passi=passi+1;
                  u=half-1;
             end
            end        
          end      
          if (pos(h)==-1) 
             pos(h)=u; 
             passi=passi+1;
          end
        end

mio

count=2;passi=0;
  for i=1:n_t  
      passi=passi+1;
    while t(i)>=x(count) & count<n
      count=count+1;
      passi=passi+1;
    end
    if count<=n
      passi=passi+1;
      ind(i)=count-1;
    end
  end

[pietro84]

Originariamente inviato da ghiotto86

trovo difficoltà nel calcolare quello che c'è dento la O tipo la ricerca binaria ha compl. O (log(n)).
la mia??

allora se non ricordo male devi calcolare il numero di passi che fa l'algoritmo in funzione della variabile n(n è la dimensione del problema). per numero di passi puoi intendere il numero di somme per esempio o il numero di confronti(dipende dall'algoritmo).

ti faccio un esempio: supponi di avere un algoritmo che stampa a video gli elementi di un vettore di n elementi in maniera sequenziale.
la dimensione del problema è n.
l'algoritmo per stampare gli n elementi fa n passi,(per passo si può intendere l'operazione di stampa a video o di lettura dell'elemento).

la complessità dell'algoritmo è n(per un vettore di n elementi fa n passi),in notazione asintotica si scrive O(n),cioè il tempo impiegato nell'esecuzione dipende linearmente dal numero di elementi che contiene il vettore.

[ghiotto86]

come vedi dagli algoritmi pietro, si effettuano meno passi con la mia routine.

[Brazorv]

nessun algoritmo di ricerca può fare meglio di O(log(n))

[pietro84]

Originariamente inviato da ghiotto86

come vedi dagli algoritmi pietro, si effettuano meno passi con la mia routine.

devi metterti a fare i calcoli per dimostrarlo! io mi scoccio sinceramente di mettermi ad analizzare gli algoritmi..

[pietro84]

Originariamente inviato da Brazorv

nessun algoritmo di ricerca può fare meglio di O(log(n))

anche questo è vero (asintoticamente)! però con n finito due algoritmi con la stessa complessità possono avere tempi di esecuzione differenti.

[ghiotto86]

Originariamente inviato da pietro84

devi metterti a fare i calcoli per dimostrarlo! io mi scoccio sinceramente di mettermi ad analizzare gli algoritmi..

non dirmelo LOL

cioè per esempio nel while della mia ricerca come faccio a calcolare le somme che si effettuano??

[pietro84]

Originariamente inviato da ghiotto86

non dirmelo LOL

cioè per esempio nel while della mia ricerca come faccio a calcolare le somme che si effettuano??

[ghiotto86]

Originariamente inviato da pietro84

ti sbatti la testa perchè è una cosa semplice oppure perchè è dura come il muro??

[pietro84]

puoi supporre che ogni iterazione sia un passo...... è anche intuitivo il calcolo.
ma sei sicuro che l'algoritmo di ricerca binaria sia scritto bene?
il tempo di esecuzione minore non è per forza indice di complessità minore però.
O(logn) è valida per valori di n molto grandi,può anche darsi che al crescere di n l'algoritmo di ricerca binaria superi il tuo! perciò devi fare il calcolo in maniera rigorosa,in prima approssimazione prendi come riferimento il numero di iterazioni che fanno i due algoritmi.

[pietro84]

Originariamente inviato da ghiotto86

ti sbatti la testa perchè è una cosa semplice oppure perchè è dura come il muro??

perchè ricordo quando studiavo per l'esame di algoritmi....e mi annoiavo a morte a calcolare la complessità