[C] Complessità operazioni su liste

[maninblack]

ciao...volevo sapere se utilizzando una struttura liste di liste e eseguendo una ricerca completa per tutta la lista più (nel caso peggiore)eseguendo una ricerca solo sulla lista pricipale, se il tempo era "teta(n)" ??!!??

[eumene]

Non credo di aver capito bene, però ci provo.

Possiedi una lista di nodi, dove ogni elemento è a sua volta una lista, creando così una sorta di "matrice"?

Inoltre non mi è chiaro questo:

eseguendo una ricerca completa per tutta la lista più (nel caso peggiore)eseguendo una ricerca solo sulla lista pricipale

Puoi definire la differenza tra "tutta la lista" e "solo la lista principale".

Per me il caso peggiore è la ricerca su tutta la struttura e non solo sulla lista principale.

E questo è il dubbio.

Tornando a quello che chiedi:

il tempo era "teta(n)" ??!!??

Dipende molto da come interpreti n e da cosa rappresenta la lista.
N è il numero di informazioni che costituiscono il tuo problema (grandezza del problema), quindi è meglio se spieghi cosa vuoi realizzare e magari posti anche l'algoritmo in PseudoCodice in modo da chiarire anche che tipo di ricerca fai (binaria - lineare; iterativa - ricorsiva)

[maninblack]

si una sorta di matrice fatta con le liste.
Questa strutture contiene delle stringhe . i nodi sulla lista principale contengono come stringa delle specie di animali e nelle relative sottoliste altri animali della stessa specie...tutto qui.
Quindi per effettuare un inserimento, dato che utilizzo le liste, sicuramente avro' un tempo lineare..ovviamente non nel caso migliore perche' sarà castante..Quello ke mi chiedo io e se il tempo di calcolo è "Ogrande"(n) oppure "teta(n)" !!! nn capisco bene la differenza!!

[ilc0rv0]

ho appena passato l'esame di algoritmi 1 con voto 29 e dovevo appunto scegliere una struttura dati per implementare 2 sotto insiemi di {1,2...n} e creare 2 algoritmi che avevano complessità pessima teta(n)
...
se non hai un universo molto grande dei dati (ma non penso che l'universo animali sia grandissimo) puoi usare una tabella a indirizzamento diretto
altrimenti prova a studiare una funzione hash, ma non so se con le stringhe sia possibile e nel caso lo fosse quanto sia facile

[maninblack]

t ringrazio del consiglio..ma nn hai risposto alla mia domanda

[ilc0rv0]

beh una ricerca in una lista ha complessità teta(n) quindi la peggiore complessità sarà sempre teta(n) a meno che nn esegui due cicli for annidati in cui in uno esegui la ricerca

[maninblack]

ma se io nell'arco di una iterazione effettuo diciamo 4 ricerche su 4 liste differenti il tempo è sempre "teta(n)"????

[ilc0rv0]

scrivi un codice esplicativo

[maninblack]

questa è una funzione dove si effettuano 4 ricerche su 3 liste differenti.ogni chiamata a funzione comprende una ricerca..Mi son incasinato col calcolo del costo perke' nn riesco a capire se è lineare o quadratico..

int ordina(char *s1,char *s2)
{
 rel1 *r1=inizioRel1;
 rel2 *r2=inizioRel2;
 rel3 *r3=inizioRel3;
 rel1 *tmp=NULL;
 rel1 *tmp1=NULL;
 rel2 *tmp3=NULL;
 rel1 *temp=NULL;

 int flag=0; //controllore. Se la prima regola non esiste sara' posto a zero altrimenti a 1
 int cont=0,cont1=0;
 char str[MAXSTRING];
 char str1[MAXSTRING];
 char str2[MAXSTRING];

 strcpy(s1,s1);
 strcpy(s2,s2);

 cont=contD;
 cont1=contB;

 if(strcmp(s1,s2)==0) //se inserisco due specie uguali esco
	 return 0;
 else

 if(r1!=NULL) //se la lista delle regole di base non è vuota inserisco in coda la nuova regola
 {
  flag=1;     //pongo a 1 il flag per dire la lista delle regole di base non è vuota
  tmp=insertRelBase(s1,s2);
  if(tmp==0)  //se il valore di ritorno è 0, vuol dire che la regola inserita era errata
	  return 1;
  else
    if(controlloRegole(r1,s1,s2)==0) //controllo se l'introduzione della nuova regola produce un ciclo o delle regole derivate corrette
    {
     printf("\n-1\n");
     cancellaCiclo(tmp); //se si verifica un ciclo cancello l'ultima regola inserita che lo ha provocato
     return 1;
    }
 }

 if(0==flag) //se flag è uguale a 0, vuol dire che la lista delle regole di base era vuota
 {
  insertRelBase(s1,s2); //inserisco la nuova regola
  insertRegole();       //la aggiungo alla lista delle regole generali
  return 1;
 }
 else  //se la lista contiene già altre regole
  {
   cont=contD;
   insertRegole();          //unisco la lista delle regole di base e quella delle derivate nella liste delle regole generali
   contrRegoleGenerale(r3); //controlle se a loro volta creano delle regole derivate
  }

 return 1;

}

[ilc0rv0]

beh io non vedo cicli:
ci sono solamente controlli if (che costano 1)

le altre operazioni sono solo inserimenti (mi pare)

e se le funzioni "contr..." (sempre che contr significo controllo, e quindi scansione di una lista) non hanno complessità maggiore di teta(n) non dovresti avere problemi