Eficiencia de programas

[telele97]

Pretendo fazer um programa que faça a intersecção dos produtos comuns que existem em 2 supermercados e depois quero genralizar para vários. Esses produtos são representados por uma lista com numeros. O código que eu tenho é o seguinte:

 lista * in2(lista *lista1, lista * lista2){
 lista * inter=NULL;
 lista *aux;
 lista *aux2;
 if(lista1==NULL || lista2==NULL)
   return NULL;
 for(aux=lista1;aux!=NULL;aux=aux->proxima){
   for(aux2=lista2;aux2!=NULL;aux2=aux2->proxima){
     if(aux->indice==aux2->indice){
       inter=insere(aux->indice, inter);
       break;
     }
   }
 }
 return inter;
}

lista * intk(lista **tabela listas, int k){
 int i;
 lista *inter;
 if(k==1)
   return *tabela[0];
 for(i=0;i<k;i++){
   inter=in2(*tabela[i], *tabela[i+1]);
 }
 return inter;
}

gostava que alguem me pudesse ajudar e me indique se existe alguma maneira de fazer isto de uma forma mais eficiente e mais rápida.

Outra questão, vi em alguns sitios para ver isto da eficiencia se costuma calcular a complexidade temporal alguem me pode dar umas dicas em relação a este assunto?

[HappyHippyHippo]

Pretendo fazer um programa que faça a intersecção dos produtos comuns que existem em 2 supermercados e depois quero genralizar para vários. Esses produtos são representados por uma lista com numeros. O código que eu tenho é o seguinte:

gostava que alguem me pudesse ajudar e me indique se existe alguma maneira de fazer isto de uma forma mais eficiente e mais rápida

se tiveres as listas ordenadas só necessitas de percorrer as listas uma vez e ao mesmo tempo, logo consegues ter um algoritmo de ordem O(n)

Outra questão, vi em alguns sitios para ver isto da eficiencia se costuma calcular a complexidade temporal alguem me pode dar umas dicas em relação a este assunto?

http://pt.wikipedia.org/wiki/Complexidade_computacional

[telele97]

se tiveres as listas ordenadas só necessitas de percorrer as listas uma vez e ao mesmo tempo, logo consegues ter um algoritmo de ordem O(n)

http://pt.wikipedia.org/wiki/Complexidade_computacional

Certo, mas no meu caso as listas não estão ordenadas e o meu algoritmo tem complexidade O(n²) certo? Compensará ordená-las e depois aplicar esse algoritmo que tu disseste?

Outra coisa o meu algoritmo para intersectar as várias lista pode ser feito assim?

[HappyHippyHippo]

Certo, mas no meu caso as listas não estão ordenadas e o meu algoritmo tem complexidade O(n²) certo? Compensará ordená-las e depois aplicar esse algoritmo que tu disseste?

sim

[telele97]

sim

Sim para as duas perguntas? Só não percebi como é que posso percorrer as lista apenas uma vez :S. Imagina "fixo" o primeiro elemento de uma lista e depois vou procurar na outra se também existe? E se encontrar passo para o outro elemento?

[HappyHippyHippo]

sim para a primeira, a segunda só verificando o código

algoritmo de intersecção de listas ordenadas

indice1 = 0
indice2 = 0
enquando (indice1 < tamanho da lista1) e (indice2 < tamanho da lista2)
 distancia = lista1[indice1] - lista2[indice2]
 se distancia == 0
   adicionar o valor à lista de interseção
   incrementar indice1
   incrementar indice2
 se distancia < 0
   incrementar indice1
 se distancia > 0
   incrementar indice2

[telele97]

sim para a primeira, a segunda só verificando o código

algoritmo de intersecção de listas ordenadas

indice1 = 0
indice2 = 0
enquando (indice1 < tamanho da lista1) e (indice2 < tamanho da lista2)
 distancia = lista1[indice1] - lista2[indice2]
 se distancia == 0
   adicionar o valor à lista de interseção
   incrementar indice1
   incrementar indice2
 se distancia < 0
   incrementar indice1
 se distancia > 0
   incrementar indice2

Certo acho que conseguir fazer mais ou menos esse código:

lista * interseccao2(lista *lista1, lista * lista2){
 lista *inter=NULL;
 lista *aux=lista1;
 lista *aux2=lista2;
 int dist=0;
 while(aux->proxima!=NULL){
   aux=aux->proxima;
 }
 while(aux2->proxima!=NULL){
   aux2=aux2->proxima;
 }
 mergesort(lista1,lista1->indice,aux->indice);
 mergesort(lista2,lista2->indice,aux2->indice);
 if(lista1==NULL || lista2==NULL)
   return NULL;
 aux=lista1;
 aux2=lista2;
 while(aux!=NULL && aux2!=NULL){
   dist=(aux->indice)-(aux2->indice);

   if(dist==0){
     inter=insere(aux->indice, inter);
     aux=aux->proxima;
     aux2=aux2->proxima;
   }else if(dist<0){
     aux=aux->proxima;
   }else {
     aux2=aux2->proxima;
   }
 }
 return inter;
}

agora tenho é um problema para escolher o algoritmo de ordenação em causa.

Suponhamos que uso o

-quicksort: -pior caso O(n²) e caso médio O(n log(n))

No pior fico com: O(2n²) da ordenação das duas listas mais O(n) do meu algoritmo de intersecção. Não sei se estou a fazer isto bem mas neste caso dava O(2n²+n) que é pior do que eu tinha.

Agora no caso médio tinha O(2nlogn)+O(n) que é bastante melhor do que eu tinha

-mergesort- este foi o melhor algoritmo que eu consegui encontrar mas também foi o que dá mais trabalho a implementar. Este algoritmo tem como pior caso e caso médio O(nlogn) ficando assim igual ao caso médio do quicksort.

Será que a melhoria é significativa na ordenação?

Gostava de uma pequena ajuda para ver se aquelas análises que fiz ali em cima se encontram correctas.

[Rui Carlos]

O quicksort é normalmente mais eficiente que o mergesort (apesar da complexidade ser ligeiramente pior).

Uma outra alternativa passa pela utilização de tabelas de hash.