Complessità computazionale del merging di due vettori

di Anonimizzato21432 il
4 risposte
/
Anonimizzato21432
Utente anonimizzato
Salve a tutti, riporto qui di seguito, scritto in pseudolinguaggio l'algoritmo che ho a disposizione per il merging di due vettori di numeri reali di dimensione rispettivamente M e N, saltando le dichiarazioni e definizioni delle variabili per praticità. 
for k=1 to M+N 
  if(i<=N AND j<= M) then 
    If (A(i) >B(j)) then 
      C(k)= B(j) 
      j=j+1 
    else 
      C(k)= A(i) 
      i= i+1 
    endif 
  else
    if (i>N) then 
      C(k)= B(j) 
      j= j+1 
    else 
      C(k)= A(i) 
      i= i+1 
    endif
  endif
endfor 
end


Dovrei stimare la complessità computazionale di questo algoritmo ma non riesco ad individuare qual è il caso peggiore e il caso migliore, qualcuno può aiutarmi? :/

4 Risposte

  • /
    Anonimizzato21468
    Utente anonimizzato
    Bhè ma ritieni ci siano casi peggiori?
  • /
    Anonimizzato21432
    Utente anonimizzato
    No, non me ne viene in mente nessuno. Nell'ipotesi che non ci sia quindi una distinzione tra caso peggiore e caso migliore, come faccio a stimare la complessità ? :/
  • /
    Anonimizzato21468
    Utente anonimizzato
    Giusto per curiosità, ma come calcoleresti la complessità, in quel caso?
    Quante volte viene eseguito il codice?
  • /
    Anonimizzato21432
    Utente anonimizzato
    M+N volte ..giusto?
Devi accedere o registrarti per scrivere nel forum
4 risposte