Gio 22 Agosto, 10:47:10 - 2019

Autore Topic: problema 1 22-02-2012 algoritmi  (Letto 1107 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline dave.pl88

  • Studente di Dottorato
  • ***
  • Post: 169
  • FeedBack: +11/-4
    • Mostra profilo
problema 1 22-02-2012 algoritmi
« il: Mer 25 Aprile, 19:11:40 - 2012 »
Scusate ma non riesco a capire bene cosa fa questo metodo

Offline dave.pl88

  • Studente di Dottorato
  • ***
  • Post: 169
  • FeedBack: +11/-4
    • Mostra profilo
Re:problema 1 22-02-2012 algoritmi
« Risposta #1 il: Mer 25 Aprile, 19:22:56 - 2012 »
rifacendolo mi pare che riordina in ordine crescente l'array, confermate??
Quanto vi vengono i costi ai punti a) e b)??

Agilulfo

  • Visitatore
Re:problema 1 22-02-2012 algoritmi
« Risposta #2 il: Mer 25 Aprile, 22:33:57 - 2012 »
si, è un algoritmo di ordinamento
in particolare è una variante di insertion sort, ricorsivo (e data la logica della ricorsione, con i record di attivazione etc etc, l'array viene ordinato dalla fine)

a) O(n^2), per ogni elemento dell'array, in mistero1(), viene chiamato mistero2() che costa nel caso peggiore O(n) (cioé quando trovo un elemento così grande da doverlo spostare fino alla fine, facendo scalare di posto tutti quelli successivi già ordinati)
edit: essendo più precisi si può dire che nel caso peggiore, array ordinato in modo decrescente, il costo totale è 1 + 2 + ... + n-1 + n = O(n^2)

b) O(n), array già ordinato dove mistero2() costa O(1) visto che un qualunque elemento è sempre più piccolo o uguale rispetto al suo successivo

c) {-2, -2, -1, 0, 3, 4}
« Ultima modifica: Mer 25 Aprile, 22:37:41 - 2012 da Agilulfo »

Offline dave.pl88

  • Studente di Dottorato
  • ***
  • Post: 169
  • FeedBack: +11/-4
    • Mostra profilo
Re:problema 1 22-02-2012 algoritmi
« Risposta #3 il: Mer 25 Aprile, 22:39:14 - 2012 »
Ok allora avevo capito anche i costi, grazie!!

Offline Alevix

  • Studente di Dottorato
  • ***
  • Post: 150
  • FeedBack: +7/-2
    • Mostra profilo
Re:problema 1 22-02-2012 algoritmi
« Risposta #4 il: Sab 16 Giugno, 12:19:27 - 2012 »
Scusate ma le domande chiedono il costo relativo alla DIMENSIONE dell'input no? perchè voi l'avete calcolato in base al VALORE dell'input?