Alberi Liste e complessità

[mjordan]

Originally posted by "SalvoX"

figurati ...non mi sono mica ikazzato per cosi poco...dicevo solo la mia

Ok

Originally posted by "SalvoX"


per la 1) sono sicuro di si

Benissimo!

Originally posted by "SalvoX"


per la 2) beh credo che si guadagni qualcosa di +(se vedicoem era il metodo lenght beh ci sono molti + confronti di un semplice assegnamento quindi credo che il guadagno ci sia..cmq tu credi di saper calcolare la complessità in questa ultima versione?
approssimativamente .....

Magari ci si può pure guadagnare qualcosa ma classicamente l'analisi della complessità va fatta a meno di una costante moltiplicativa, quindi una complessità O(100n) e O(50n), per quanto sia + veloce la seconda, a livello formale sono del tutto equivalenti. Questa considerazione va fatta anche durante l'analisi vera e propria, quindi non ti conviene considerare i termini costanti, bensi solamente i fattori predominanti. Questo è importante per 2 motivi: uno riduce la difficoltà dell'analisi, secondo uniforma ipotetici algoritmi in base al loro limite asintotico.

Originally posted by "SalvoX"


cmq tanto per dirti ho provato a fare un metodo per fare lo swap di due oggetti tipo Nodo (doppio o semplicemente linkato) e viene davvero difficile e lungo quindi credo che userò sempre questo sistema per gestire la struttura dati in questione come fosse un array..che ne dici?
grazie dele tue risposte

Non ho capito bene cosa intendi quando dici di usare la struttura dati come se fosse un array. Considera comunque che questa "composizione di strutture", in questo caso una lista di alberi, è solo un bell'esercizio di programmazione. Nella pratica ha ben poca utilità (scusa, nessuna utilità) nonchè poco senso utilizzare una lista di alberi binari.

Ciao.

[SalvoX]

mi riferivo al fatto di poter accedere ad un qualsiasi oggetto della lista in tempo lineare O(n) come avviene per un array
solo mettendo i puntatori su un array di oggetti posso fare ciò e quindi uso questo metodo per gli esercizi dove mi serve

Sulla poca utilità di quello che faccio tramite sta meteria non avevo alcun dubbio
cmq serve per fare pratica col linguaggio questo si

Grazie delle info
a presto

[cionci]

Se è per questo un albero binario (soprattutto se completo) si può memorizzare tranquillamente in un vettore

[mjordan]

Originally posted by "SalvoX"

mi riferivo al fatto di poter accedere ad un qualsiasi oggetto della lista in tempo lineare O(n) come avviene per un array
solo mettendo i puntatori su un array di oggetti posso fare ciò e quindi uso questo metodo per gli esercizi dove mi serve

Stai attento ad usare questa soluzione. Moli professori se gli cambi la struttura dati ti bocciano senza riserva, anche se quello che hai scritto merita il premio Turing.

Originally posted by "SalvoX"


Sulla poca utilità di quello che faccio tramite sta meteria non avevo alcun dubbio
cmq serve per fare pratica col linguaggio questo si

Aspetta la materia è fondamentale, è la lista di alberi che non serve a una mazza

Originally posted by "SalvoX"


Grazie delle info
a presto

Figurati.

P.S.:Ho provato BugSeeker 2. Funziona bene, ma dopo che l'ho usato e lo chiudo, mi pianta l'intero computer, mouse compreso. Con Linux invece funziona bene. Succede anche a te?

[SalvoX]

no a me non capita

cmq tornando al discorso dell'array di oggetti cosa altro potrei fare per raggiungere l'obbiettiovo?

[mjordan]

Originally posted by "SalvoX"

no a me non capita

cmq tornando al discorso dell'array di oggetti cosa altro potrei fare per raggiungere l'obbiettiovo?

Attenerti scrupolosamente a quello che richiede il testo
Non che non vada bene usare l'array, ma se il prof. vuole che utilizzi una lista concatenata non ti conviene usare qualcosa di diverso...

[SalvoX]

si ma il insertion sort parla chiaro..devo accedere a un oggetto j-1 senza poter neanche avere un campo prev per tornare indietro (lista semplice ha solo next) ...non vedo molte alternative...la prima versione aveva metodo index ma la complessità veniva n^3 ...e non gli andava bene

mah che so a sto punto boh non so cosa inventarmi

[mjordan]

Originally posted by "SalvoX"

si ma il insertion sort parla chiaro..devo accedere a un oggetto j-1 senza poter neanche avere un campo prev per tornare indietro (lista semplice ha solo next) ...non vedo molte alternative...la prima versione aveva metodo index ma la complessità veniva n^3 ...e non gli andava bene

mah che so a sto punto boh non so cosa inventarmi

Ma quindi non è richiesto di usare esplicitamente una lista...

[SalvoX]

"Definire una classe Java TreeList per una lista linkata semplice in modo che i singoli nodi possano contenere radici di alberi binari.
Scrivere un metodo Java per la classe TreeList che ordini la lista conl'algoritmo dell'Insertion Sort in base alle altezze degli alberi"

[cionci]

Allora non va bene nemmeno il vettore che contiene le radici...

[SalvoX]

quindi questo programma è infattibile?

(da notare che cmq avevo publicato la prima soluzione senza array di oggetti e funzionava ..ma ripeto una complessità cubica è troppo alta)

[cionci]

Fino a quando sei obbligato ad usare un lista per l'albero ed una lista per per le teste di albero credo che sia impossibile avere una complessita inferiore a O(N^3)...

[/\/\@®¢Ø]

Scusate... forse non ho capito io il problema, ma la soluzione che avevo proposto io non andava bene ?

Facendo prima una scansione degli alberi per trovare le dimensioni, poi fare l'ordinamento e' come
fare un insertion sort su normali interi, o no ?
Qualcosa del tipo

class TreeList
{
 public TreeList next;
 public int height;
 public Tree root;

 public static void sort( TreeList begin )
 {
    TreeList x = begin;
    while( x != null )
    {
       x.height = x.root.height();
       x = x.next;
    }
    insertionSort( begin );
}

ed insertion sort opera normalmente usando il campo height per il confronto.
O e' proprio implementare quest'ultimo con liste che ti da problemi ?
Una possibile implementazione e' la seguente:

   void insertionSort( TreeList begin )
   {
      if ( begin == null )
 return;
      // prima ordiniamo il resto della lista
      insertionSort( begin.next );

      // ora inseriamo il nuovo elemento
      while( begin.next != null )
      {
         if ( begin.height > begin.next.height )
         { // swap altezza 
            int tmp = begin.height
            begin.height = begin.next.height;
            begin.next.height = tmp;
            // swap radice
            Tree tmp2 = begin.root;
            begin.root = begin.next.root;
            begin.next.root = tmp2;
            begin=begin.next;
         }
      }
    }

Tieni presente che e' un po' che non scrivo Java e quindi e' possibile che somigli piu' a codice C++ .
L'idea comunque e' che dovendo operare su liste e nmon su di un array, la cosa piu' semplice e'
operare per ricorsione. L'algoritmo di solito parte partendo con due elementi, ordinandoli e
aggiungendo poi man mano gli altri. In questo caso e' lo stesso, solo che l'array e' ordinato
a partire dal fondo invece che dall'inizio: la chiamata ricorsiva scorre la lista fino agli ultimi due elementi,
li ordina e poi torna; ritorna all'elemento precedente, lo inserisce e ritorna, e cosi' via finche'
alla fine non fa che inserire l'ultimo elemento (ovvero il primo della lista).
Non e' un algoritmo da manuale, ma e' insertion sort al 100%.



Edit: ovviamente non potevo non fare errori . Corretti (quelli che ho visto )
Ri-Edit: corretto un piccolo bug ( non scambiavo le radici... )