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]

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]

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]

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]

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]

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 :sofico: tipo la ricerca binaria ha compl. O (log(n)).
la mia??

[mpattera]

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

[ghiotto86]

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]

trovo difficoltà nel calcolare quello che c'è dento la O :sofico: 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]

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

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

[pietro84]

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

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

[ghiotto86]

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

non dirmelo LOL :sofico:

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

[pietro84]

non dirmelo LOL :sofico:

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

[ghiotto86]

:muro: :D

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

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

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

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

[Brazorv]

scusate l'ignoranza ma mi spiegate come funziona questo ciclo?

for i=1:n_t

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

mi autoquoto perchè credo che leggendo questo post si capisca bene come si deve fare...

[pietro84]

scusate l'ignoranza ma mi spiegate come funziona questo ciclo?

for i=1:n_t

trduzione in C:
for(i=1;i<=n_t;i++)

[sottovento]

Scusami, ma se hai ottenuto una ricerca con complessita' inferiore a O(log n) mi sembra un risultato degno di nota.
Insomma, da pubblicare. Ne sei sicuro?
Io so che in alcuni casi (magari con piu' informazioni sui dati a disposizione) e' possibile trovare degli algoritmi O (log log n).

Ho provato a guardare il codice (ammetto, di fretta) ma non l'ho capito bene. Puoi spiegarlo e magari farne un pseudo codice? Oppure riscriverlo in C?
Qual e' il criterio che utilizzi per ridurre le passate?

High Flying
Sottovento

[ghiotto86]

raga penso che non ho scoperto nulla di eccezionale :D
l'algoritmo che ho fatto serve soltanto a trovare, dato un vettore x e un vettore t, in che intervallo cade il t-esimo elemento nel vettore x.
per esempio:

x=[1 4 6 9];
t=[1 2 3 4 5 6 7 8 9];

per ogni elemento di t devo vedere in che intervallo cade in x:

il 1° el di t cade nel 1° intervallo il 2° el di t cade sempre del primo e così via;
alla fine mi ricavo un vettore con tutti gli intervallo e deve essere così per l'esempio fatto,

1 1 1 2 2 3 3 3 3

tutto qui.
per risolvere questo problema si può utilizzare la ricerca binaria oppure l'algoritmo che ho fatto io

[ghiotto86]

ah scusate è linguaggio matlab.

[ghiotto86]

mi autoquoto perchè credo che leggendo questo post si capisca bene come si deve fare...

quindi devo tener conto soltanto dei loop e non dei confronti

[ghiotto86]

è una domanda :sofico:

[The3DProgrammer]

quindi devo tener conto soltanto dei loop e non dei confronti


nella complessità asintotica si.

Ti faccio un esempio:

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
for(int k=0; k<n; k++){

...do something...
}

....

for(int i=0; i<n; i++)
for(int j=0; j<n; j++){

}



supponendo ke questi for innestati facciano parte di un ipotetico algoritmo, e che all'interno dei due for + interni vengano eseguite solo operazioni semplici,

puoi valutare la complessità di questo ipotetico algoritmo come:

f(n)=k*n^3+t*n^2 (dove k e t sono costanti dipendenti dall'algoritmo)

Nella complessità asintotica xò si considerano solo i termini con esponente + grande, motivo x cui la complessità asintotica nel caso peggiore di questo algoritmo sarebbe O(n^3).

ciao

[The3DProgrammer]

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

Ovviamente c'è differenza tra la complessità di un algoritmo e la complessità (intrinseca) di un problema. Come giustamente dice Brazorv, la complessità intrinseca (lowerbound) del problema "ricerca di un elemento in un insieme ordinato di elementi" è omega(log(n)), x cui, mi spiace darti una brutta notizia, ma è impossibile che il tuo algoritmo abbia una complessità asintotica minore di log(n) :)

ciauz

[ghiotto86]

non sto cercando di fare un algoritmo con complessità minore di log(n) :D ci mancasse.

per il fatto della complessitàò temporale per ogni for ho capito come si calcola, ma per esempio nel mio caso quando ho

while t(i)>=x(count) & count<n
count=count+1;
end

come faccio a calcolare la sua complessità temporale??

questo è l'algoritmo


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


grazie

[pietro84]

non sto cercando di fare un algoritmo con complessità minore di log(n) :D ci mancasse.

per il fatto della complessitàò temporale per ogni for ho capito come si calcola, ma per esempio nel mio caso quando ho

while t(i)>=x(count) & count<n
count=count+1;
end

come faccio a calcolare la sua complessità temporale??

questo è l'algoritmo


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


grazie


se quel while è innestato nel ciclo for moltiplichi il numero di iterazioni effettuate dal ciclo while per il numero di iterazioni effettuate dal ciclo for

[The3DProgrammer]

non sto cercando di fare un algoritmo con complessità minore di log(n) :D ci mancasse.

per il fatto della complessitàò temporale per ogni for ho capito come si calcola, ma per esempio nel mio caso quando ho

while t(i)>=x(count) & count<n
count=count+1;
end

come faccio a calcolare la sua complessità temporale??

questo è l'algoritmo


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


grazie

ti do un suggerimento: per la complessità asintotica, valuta il caso peggiore, cioè il caso in cui il tuo algoritmo sarà costretto ad effettuare il massimo numero di operazioni, a causa della particolare conformazione dei dati in input:)

[okay]

non sto cercando di fare un algoritmo con complessità minore di log(n) :D ci mancasse.

per il fatto della complessitàò temporale per ogni for ho capito come si calcola, ma per esempio nel mio caso quando ho

while t(i)>=x(count) & count<n
count=count+1;
end

come faccio a calcolare la sua complessità temporale??

questo è l'algoritmo


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


grazie





Innanzitutto devi fare in modo di far andare il tutto sia su pc lenti che su pc veloci.
Devi calcolare il tempo di passata per tutti in pc in modo uguale per avere risultati corretti.

Quindi:






count=2;passi=0;
for i=1:n_t

if(Frame(t_RATE)) //t_RATE = 60
{
while t(i)>=x(count) & count<n
//calcola il tempo per il ciclo con count
float newTime = time();
float dt = newTime - currentTime;
currentTime = newTime;
t += dt;
count=count+1;
end
if count<=n
//calcola il tempo per il ciclo con count-1
float newTime1 = time();
float dt = newTime1 - currentTime1;
currentTime1 = newTime1;
t1 += dt;
ind(i)=count-1;
end
end
}

BOOL Frame(int Rate)//Rate = 60 frame
{
static float lastTime = 0.0f
elapsedTime = 0.0;

currentTime = timeGetTime() * 0.001f;

elapsedTime = currentTime - lastTime;

if( elapsedTime > (1.0f / Rate) )
{
lastTime = currentTime;
return TRUE;

}


Ecco ora avrai t che è il tempo del primo ciclo e t1 che è il tempo del secondo.
Ma l'importante è che i tempi del calcolo delle routine li puoi avere perfetti per tutti i pc sia quelli lenti che quelli superveloci dove i tempi sono rispettati.

Anzi non sono proprio perfetti, mi correggo, ma è il modo di calcolare giusto ciò che hai chiesto...... se ho capito bene ciò che intendevi!!

per avere la perfezione devi aggiungere un controllo sui frames come si usa per simulare la fisica in particolar modo nella fisica per i videogame in quanto si può avere un abbassamento del fps per tante e varie ragioni tipo esplosioni non perfettamente temporali e/o fisica non proprio corretta.

quindi ecco un esempio di algoritmo per correggere in modo perfetto i frame
(nel tuo caso... per stare in modo corretto nei cicli mentre per quello che faccio io serve per calcolarmi la fisica nei 1/60 frame che uso, ma secondo me, se non ho capito male è adatto cmq al tuo scopo sempre che abbia capito ciò che devi fare):

float t = 0.0f;
const float dt = 0.01f;

float currentTime = 0.0f;
float accumulator = 0.0f;

State previous;
State current;

while (!quit)
{
float newTime = time();
float deltaTime = newTime - currentTime;
currentTime = newTime;

accumulator += deltaTime;

while (accumulator>=dt)
{
previousState = currentState;
integrate(currentState, t, dt);
t += dt;
accumulator -= dt;
}

const float alpha = accumulator / dt;

State state = currentState*alpha + previousState*(1.0f-alpha);

render(state);
}


p.s. fai delle prove e facci sapere se è ok

Mentre per quanto riguarda la complessità temporale di eventi nell'algoritmo, per esempio vettori come hai scritto sopra, puoi usare il tempo prendendo l'istante appunto tempo t(x) e metterlo in un vettore (sempre calcolando il tutto con il tempo) e alla fine osservare l'indice del vettore e vedere il suo valore di tempo computazionale.
Aggiungo sempre se ho capito bene

[ghiotto86]

grazie a tutti raga:

allora cominciamo

x okay:
si in pratica con matlab ho testato quanto tempo ci mettevano i 2 algoritmi per gli stessi valori di input ed effettivamente va + veloce il mio, anche perchè quello della ricerca binaria fa + passi.
ps: mi piace sto fatto della fisica :D

x pietro:
si avevo fatto quel pensiero :D
la complessità temp in prativa sarà n* (complessità del while) giusto??

x 3d programmer:
una volta fatto il caso peggiore (che secondo me è che nel while t(i) sia sempre >=x(count) giusto??)
che faccio??
tengo presente solo del caso peggiore??

[leadergl]

x pietro:
si avevo fatto quel pensiero :D
la complessità temp in prativa sarà n* (complessità del while) giusto??

non credo...perchè la complessità del While varia a seconda del valore!


x 3d programmer:
una volta fatto il caso peggiore (che secondo me è che nel while t(i) sia sempre >=x(count) giusto??)
che faccio??
tengo presente solo del caso peggiore??

ti consiglio di seguire la strada che suggerisce The3DProgrammer, ovvero di dare una stima della complessità del tuo algoritmo sia nel caso migliore che nel caso peggiore...poi il caso medio lo dovresti fare o su base statistica con dei dati alla mano o lo tiri fuori dalla media dei due casi precedenti...


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

che equivale a:

======================================================
ALGORITMO | COMPL
======================================================
Count=2; (1)
Passi=2; (1)
FOR i=1 to N_T (n*...
WHILE (T(i) >= x(Count)) & (Count<n)
Count=Count+1; CasoMigliore: 0, CasoPeggiore: len(x)-1
END WHILE
IF Count<=N THEN
ind(i)=Count-1; (2)
END FOR

Credo che bene o male vada analizzato così...anche se al momento non ricordo troppo :p

cmq non capisco a che serve:
1) Passi=2;
2) IF Count<=N THEN ind(i)=Count-1;
visto che "Passi" non viene mai usato e che invece quell'IF viene eseguito credo sempre...ed un IF che viene eseguito sempre non serve a nulla...

[dierre]

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

guarda che devi esaminare il caso peggiore, e dubito sia migliore di O(log(n))

[ghiotto86]

hai ragione leader quell'if non serve proprio, era un controllo che mi serviva insieme a un altro pezzo di codice che ho eliminato dopo. :D
anche passi è inutile.

quindi ricapitolando, la complessità sarà n* media tra complessità minore e maggiore del while che come vedo è len(x)-1 ??

[ghiotto86]

guarda che devi esaminare il caso peggiore, e dubito sia migliore di O(log(n))

lo so mi sembra anche a me improbabile.
ma il fatto è che testando le due velocità va + veloce il mio, anche xche il mio algoritmo non è una vera e propria ricerca.

[pietro84]

lo so mi sembra anche a me improbabile.
ma il fatto è che testando le due velocità va + veloce il mio, anche xche il mio algoritmo non è una vera e propria ricerca.

ma non c'entra neinte O(log(n)) tu hai usato la ricerca binaria per fare un'altra cosa,non hai utilizzato la ricerca binaria e basta...il primo algoritmo non consiste solo in una ricerca binaria(non penso che abbia complessità log(n) ) ,perciò il tuo è più veloce. :D
se dovessi scrivere un algoritmo di ricerca con complessità minore di quella dell'alg di ricerca binaria ti sarebbe impossibibile :muro:

[ghiotto86]

ma non c'entra neinte O(log(n)) tu hai usato la ricerca binaria per fare un'altra cosa,non hai utilizzato la ricerca binaria e basta...il primo algoritmo non consiste solo in una ricerca binaria(non penso che abbia complessità log(n) ) ,perciò il tuo è più veloce. :D
se dovessi scrivere un algoritmo di ricerca con complessità minore di quella dell'alg di ricerca binaria ti sarebbe impossibibile :muro:

bhe si l'algoritmo che ho scritto al 1° post fa esattamente la ricerca binaria.
soltanto c'è una modifica alla fine se vedi.
ma in fin dei conti è una ricerca binaria, almeno credo :D

[dnarod]

la complessita è uno degli argomenti piu palla che si possono studiare...meno male che anche all uni non la si tratta che in po chi esami, senno uno sclererebbe...

[ghiotto86]

la complessita è uno degli argomenti piu palla che si possono studiare...meno male che anche all uni non la si tratta che in po chi esami, senno uno sclererebbe...

ti quoto.
però a dir la verità è anche uno dei pochi interessanti. :D

[EnderIII]

Ghiotto86, forse ho capito qual'è il tuo problema, ed ho la risposta.

Tu hai il vettore x già ordinato. Quindi prendi un elemento da il vettore t e vuoi sapere in che intervallo si trova, il che equivale a dire a trovare la posizione nel vettore x dell'elemento immediamente inferiore e di quello immediatamente superiore.

Questo problema è analogo a quello di cercare l'elemento di t nel vettore x. Te in pratica lo risolvi con una ricerca lineare, mentre l'altro codice usa una ricerca binaria.

Per farti un'esempio banale (scusa la pedanteria) se te pensi un numero da 1 a 1000, io sono sicuro di indovinarlo con 10 domande applicando una ricerca binaria (supponi tu abbia pensato 4):

io: è inferiore a 500? Sì. Allora è nell'intervallo 1, 499.
io: è inferiore a 250? Sì. Allora è nell'intervallo 1, 249.
io: è inferiore a 125? Sì. Allora è nell'intervallo 1, 124.
io: è inferiore a 63? Sì. Allora è nell'intervallo 1, 62.
io: è inferiore a 32? Sì. Allora è nell'intervallo 1, 31.
io: è inferiore a 16? Sì. Allora è nell'intervallo 1, 15.
io: è inferiore a 8? Sì. Allora è nell'intervallo 1, 7.
io: è inferiore a 4? No. Allora è nell'intervallo 4, 7.
io: è inferiore a 6? Sì. Allora è nell'intervallo 4, 5.
io: è inferiore a 5? Sì. Alora è 4.

Totale passi 10.

Poteva andarmi meglio con la ricerca lineare...

io: è 1? No.
io: è 2? No.
io: è 3? No.
io: è 4? Sì.

Totale passi 4.

Ma se pensavi 999...

Per quanto rigurda la questione che il tuo codice è più veloce dipende dalla ridotte dimensioni del vettore x.

Supponamo che il codice tuo ha complessita n mentre l'altro ha complessità 10log(n) il tuo sarà più veloce finché n < 10log(n), ossia finche n < 59, ossia finche il vettore x ha meno di 59 elementi.

[ghiotto86]

hai perfattamente capito che fa il mio 2° algoritmo:

//imposto count a 2
count=2;

//per ogni valore del vettore t
for k=1:n_t

//se il valore k-esimo del vettore t non è nell'intervallo attuale allargo l'intervallo
while t(k)>=x(count) & count<n
count=count+1;
end
//vettore degli intervalli è count-1
ind(k)=count-1;
end

quello che non mi spiego io è che testando con matlab le due funzioni aumentanto anche gli elementi di x il 2° algoritmo è nettamente + veloce :muro:

[rdefalco]

NOTA: sto studiando Algoritmi e Strutture Dati in questi giorni quindi sto a mente fresca...
:sofico:

DOMANDA: Ma i due array sono ordinati? O uno dei due lo è? Dal tuo esempio a pagina 2 sembra di sì, in quel caso intuitivamente direi che la complessità si può ottenere O(n) e credo anche in modo abbastanza semplice, nel caso non siano ordinati non si potrebbe fare la ricerca binaria (ovviamente).

[rdefalco]

Ah, il calcolo della complessità asintotica non si fa assolutamente provando l'algoritmo, ma solo con l'analisi del codice. Ovviamente per chi (come pure io) ama programmare non c'è niente di meglio che testare "sul campo" un algoritmo ma purtroppo... :fagiano:

In genere (ad esempio sugli algoritmi di ordinamento basati su confronti) si contano i confronti, oppure le operazioni elementari (addizioni, moltiplicazioni* ecc)

* per le moltiplicazioni su numeri grandi sarebbe un discorso a parte...

[EnderIII]

Devi controllare gli incrementi relativi non quelli assoluti. Esempio:

se con x di dimensione 10 Tempo(tuo codice)/Tempo(ricerca binaria) = 0.2,

con x di dimensione 20 devi osservare un aumento di questo valore e così via finche il rapporto supera l'unità.

[ghiotto86]

NOTA: sto studiando Algoritmi e Strutture Dati in questi giorni quindi sto a mente fresca...
:sofico:

DOMANDA: Ma i due array sono ordinati? O uno dei due lo è? Dal tuo esempio a pagina 2 sembra di sì, in quel caso intuitivamente direi che la complessità si può ottenere O(n) e credo anche in modo abbastanza semplice, nel caso non siano ordinati non si potrebbe fare la ricerca binaria (ovviamente).


si i due array sono ordinati

[rdefalco]

Non ho capito molto bene il codice perché ci trovo delle variabili non inizializzate che non capisco cosa intendano (n_t). Comunque: il problema NON E' la ricerca binaria. Quella ha tempo O(logn) e non si può cambiare. Ma qui stiamo parlando di DUE array ordinati che in qualche modo si devono confrontare. Essendo ordinati, presumiamo che si proceda andando sempre avanti, mai indietro.

Quindi dati n e m rispettivamente indicanti la dimensione dell'array A e dell'array B un algoritmo ottimo avrà tempo O(n+m) che poi è O(max(n,m)) cioè limitato superiormente al maggiore fra i due.

Se UNO SOLO dei due era ordinato (A) e l'altro no (B) avremmo dovuto usare tecniche di ricerca (quindi ricerca binaria) per cercare, per ogni elemento dell'array B, il suo posizionamento nell'array ordinato A. Quindi avremmo usato tempo O(log(n)) per cercare OGNUNO degli "m" elementi, quindi il tempo di un algoritmo ottimo sarebbe O(m·log(n)).

Adesso passiamo a vedere il tuo codice.


count=2;passi=0;

## le istruzioni in questo for vengono eseguite n_t volte

for i=1:n_t
passi=passi+1;

## il while AL PIU' viene eseguito finché count non raggiunge n
## ma count non viene azzerato fra un while e l'altro quindi in TOTALE
## le istruzioni in questo while saranno eseguite O(n) volte pur essendo
## innestate in un for

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


Quindi pur essendo un algoritmo con due iterazioni innestate (for e while) in realtà esse non fanno moltiplicare la complessità, in quanto il while è condizionato da count che può solo essere incrementato ma non scende mai (parte da 2 e termina a n). Il for viene ripetuto n_t volte (che credo sia la "m" del mio esempio sopra. Quindi la complessità totale è O(n+n_t) che è uguale a O(max(n,n_t)), quindi prende tempo lineare rispetto alla dimensione del più grande dei due array.

[rdefalco]

DISCLAIMER: non mi ritengo responsabile per qualsiasi strafalcione algoritmico che io possa aver inserito in quanto sopra :D e soprattutto non ho mai visto prima codice Matlab, quindi il tutto è frutto di una mia personale interpretazione del codice. Saluti a tutti :D