complessità ??

[pavimento]

Ciao a tutti

Se ho una struttura formata da una lista di alberi,cioè in cui ogni nodo della lista contiene un albero binario,la complessità (nell'inserimento) è n*logn??

E se per la lista faccio in modo che non debba scorrerla tutta ogni volta che faccio un inserimento(inserimento che faccio sempre in coda),mantenendo un puntatore sull'ultimo nodo, la complessità diventa
O(costante)??

Se è così la complessità totale diventerebbe costante*logn o rimarebbe comunque n*logn??


E se nella stessa lista oltre che all'albero avessi un'altra lista dello stesso tipo diventerebbe costante*(costante+logn) o n*(n+logn) o altro??

Grazie!!

Ciao

pavimento

[sottovento]

Ciao

Non ho capito perche' dici che la complessita', per l'inserimento in btree, e' n*log(n). In realta' devi solo scendere attraverso l'albero di n elementi, per cui e' semplicemente O(log n).

Nel caso si debba scorrere anche la lista, allora la complessita' di tutto l'algoritmo e' O(n * log n), come da te rilevato.

Se inserisci solo in coda, allora tutto l'algoritmo sara' O(log n)

L'ultima domanda non l'ho capita: intendi se avessi una lista di liste, quest'ultima contenente un btree? In questo caso, assumendo la scansione di liste (no puntatori all'ultimo elemento) la complessita' di tutto l'algoritmo sarebbe O(n^2 * log n).

High Flying
Sottovento

[pavimento]

ciao!
Grazie!!

per l'ulitma domanda provo a spiegarmi meglio..


se ho una cosa come
/**********************************/
typedef struct lista{
struct albero *a;
struct lista *next;
struct lista *prec;
struct lista_2 *b;
}lista;


typedef struct lista_2{
int a;
struct lista *next;
struct lista *prec;
}lista_2;





/****************************/

dove sia in lista che in lista_2 inserisco in coda.

La complessità nell'inserimento dello stesso elemento sia nella
lista b che nell'albero è O(logN) ?(se ho capito dalle risposte che mi hai dato prima dovrebbe esser così..)??


Se però non faccio l'inserimento in coda in nessuna delle due diventa
n*(n+logn) ??o no?..

Grazie Mille :)

Ciao
pavimento

[leadergl]

Io però non credo che la tua struttura si una lista di alberi binari....


Struttura AlberoB
Nodo
Successivo (di tipo AlberoB)
Precedente (di tipo AlberoB)
Fine Struttura AlberoB

Struttura Lista
Elemento (di tipo AlberoB)
Successivo (di tipo Lista)
Fine Struttura Lista

credo che questa sia una lista di Alberi Binari....


-------- AGGIUNTA ---------
mi ero perso il pezzo di inserire nella lista un altro elemento dello stesso tipo...la struttura Lista diventerebbe così:

Struttura Lista
Elemento1 (di tipo AlberoB)
Elemento2 (di tipo AlberoB)
Successivo (di tipo Lista)
Fine Struttura Lista

in ogni caso dubito andresti a migliorare...devi lavorare sull'algoritmo che usi per gestire le tue strutture...

[sottovento]

Scusa leadergl, ma a me la struttura sembra corretta. Pavimento non ha riportato informazioni sulla definizione della struct albero, ma confiderei nella sua correttezza.

Ad ogni modo: viste le strutture, se inserisci in coda senza quindi scandire alcuna lista, il tempo di inserimento e' costante.
Dato il numero n di elementi, non hai alcuna relazione con esso, percio' la tua complessita' e' O(1). La complessita' di inserimento nell'albero binario resta ovviamente O(log n), per cui quest'ultima risultera' essere anche quella totale.

High Flying
Sottovento

[leadergl]

Scusa leadergl, ma a me la struttura sembra corretta. Pavimento non ha riportato informazioni sulla definizione della struct albero, ma confiderei nella sua correttezza.


Scusa ma io per una "lista di interi" intendo una struttura formata da due campi di cui uno è di tipo intero o l'altro è un puntatore ad una struttra dello stesso tipo.

Di conseguenza una "lista di alberi binari" avrà due campi di cui uno è di tipo "albero binario" e l'altro è un puntatore ad una struttura dello stesso tipo.

e queste:

typedef struct lista{
struct albero *a;
struct lista *next;
struct lista *prec;
struct lista_2 *b;
}lista;


typedef struct lista_2{
int a;
struct lista *next;
struct lista *prec;
}lista_2;
non credo siano "liste di alberi binari" a prescindere dalla sua struttura albero...

io vedo solo una struttura tutta incasinata che già per il fatto di avere in entrambe le strutture puntatori a "next" e "prec" mi porta lontano dall'idea di lista....

poi non so, magari ho capito male io quello che si voleva ma nel suo primo messaggio leggo:

Ciao a tutti

Se ho una struttura formata da una lista di alberi,cioè in cui ogni nodo della lista contiene un albero binario,la complessità (nell'inserimento) è n*logn??
......
E se nella stessa lista oltre che all'albero avessi un'altra lista dello stesso tipo diventerebbe costante*(costante+logn) o n*(n+logn) o altro??