[C] Complessità computazionale: fusione di due array ordinat

di Anonimizzato15994 il
4 risposte
/
Anonimizzato15994
Utente anonimizzato
Salve a tutti, avendo implementato un algoritmo che riguarda la fusione di due array ordinati con m != n ( dove m ed n sono rispettivamente il numero di componenti dell'array), sapendo che in questo caso la loro complessità computazionale espressa in tempo nel caso peggiore è di O(n+m), vorrei sapere invece quanto vale la complessità di quest'algoritmo nei casi:
1 - m=n
2 - m > n dove in questo caso m è strettamente maggiore di n
3 - n > m " " n " m

4 Risposte

  • Molto attivo
    Iscritto da
    set, 2014
    Messaggi
    535
    Conosci i simboli di landau?

    Per la complessità i ragionamenti che si fanno sono identici a quelli che si fanno in analisi con i simboli di landau per l'O-grande, quindi:

    1) m=n ==> O(n+m) = O(2n) ma da un punto di vista ingegneristico è uguale a O(n)
    2) m>n ==> O(n+m) ma da un punto di vista ingegneristico è uguale a O(m)
    3) Non ho capito la domanda!
  • /
    Anonimizzato15994
    Utente anonimizzato
    Non ho ancora fatto analisi, quindi non conosco i simboli di landau, comunque ti ringrazio per le risposte, la terza è come la secondo ma con m ed n invertite
  • Molto attivo
    Iscritto da
    set, 2014
    Messaggi
    535
    Bene! Allora la risposta è uguale alla 2) con m e n invertite.
  • /
    Anonimizzato15994
    Utente anonimizzato
    Sempre gentilissimo ti ringrazio
Devi accedere o registrarti per scrivere nel forum
4 risposte