Jump to content

ver o tempo de custo de um determinado algoritmo


Flames
 Share

Recommended Posts

Boas pessoal!

Tenho o seguinte código...

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Max 10
int bubble(int vect[], int n);
int seleccao (int vect[], int n);
void funcaoimprime(int vect[], int n);
int main()
{
    int i;
    long timeinicial,timefinal;
    int diferencatime;
    int n=Max;
    int vetor[Max-1];
    srand(time(NULL)); /*gerar a seed*/
     for (i=0; i<Max-1; i++)
     {
           vetor[i]= rand();
      }
/*FUNCAO SELECCAO TEMPO*/
     timeinicial=time(NULL);
     seleccao(vetor,n);
     timefinal=time(NULL);
     printf("%d",diferencatime=timefinal-timeinicial);
/*Fim do calculo funcao seleccao*/
/*Funcao Buble neste caso esta tudo ja ordenado*/
     timeinicial=time(NULL);
     bubble(vetor,n);
     timefinal=time(NULL);
     printf("%d",diferencatime=timefinal-timeinicial);
/*Fim do calculo funcao buble*/

}

int bubble(int vect[],int n)
  {
        int i,j,t;
         for(i=n-2;i>=0;i--)
         {
            for(j=0;j<=i;j++)

                  {
                    if(vect[j]>vect[j+1])
                        {
                            t=vect[j];
                            vect[j]=vect[j+1];
                            vect[j+1]=t;
                        }
                   }


           }/*end for 1.*/

  }
int seleccao (int vect[], int n)
{
    int k, indx, j, maior;
    for (k=n-1; k>0; k--) {
        maior = vect[0]; indx = 0;
        for (j=1; j<=k; j++)
            if (vect[j] > maior) {
                maior = vect[j];
                indx = j;
                }
    vect[indx] = vect[k];
    vect[k] = maior;
}

}



void funcaoimprime(int vect[], int n){
     int i;
     for (i=0; i<n; i++)
         printf("%d = %d\n", i, vect[i]);
}



A minha questão prende-se com o seguinte:

Tenho que testar o tempo, que custa a executar algumas funcoes de "ordenamento", de um vetor com 10000 valores aleatorios lá dentro...

O meu problema é que depois de usar uma funcão o vector fica todo ordenado. O melhor para este caso é fazer "copias" do vector original, para poder fazer essas comparacoes em cada uma das funcoes e no fim dar-me o tempo de custo de cada funcao?

Link to comment
Share on other sites

O meu problema é que depois de usar uma funcão o vector fica todo ordenado. O melhor para este caso é fazer "copias" do vector original, para poder fazer essas comparacoes em cada uma das funcoes e no fim dar-me o tempo de custo de cada funcao?

Sim, mas faz so uma copia (de cada vez).

#include <string.h> /* memcpy() */
    int vetor[Max-1];
    int copia[Max-1];
    /* ... inicializa vetor ... */
    /* copiar para copia */
    memcpy(copia, vetor, sizeof copia);
    /* ... ordena vetor ... */
    /* copiar para vetor */
    memcpy(vetor, copia, sizeof copia);
    /* ... */

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Sim, mas faz so uma copia (de cada vez).

#include <string.h> /* memcpy() */
    int vetor[Max-1];
    int copia[Max-1];
    /* ... inicializa vetor ... */
    /* copiar para copia */
    memcpy(copia, vetor, sizeof copia);
    /* ... ordena vetor ... */
    /* copiar para vetor */
    memcpy(vetor, copia, sizeof copia);
    /* ... */

Pmg fazer uma funcao para fazer a copia um a um como é para muitos numeros iria-me custar algum tempo computacional? memcpy é a melhor forma?

memcpy(vetor, vetororiginal, Max*sizeof(int));  

Tive a procura e memcpy da forma que disseste não estava a copiar o ultimo index só assim me deu ...

Link to comment
Share on other sites

Para mim, o memcpy() funciona como eu disse (podes ver exemplo no ideone).

Deves estar a fazer qualquer coisa mal.

Reapara que ao definires os arrays como

int copia[Max - 1];

eles tem elementos desde o indice 0 até ao indice Max - 2. O indice Max - 1 nao existe.

A tua instrucao

memcpy(vetor, vetororiginal, Max * sizeof(int));

vai tentar aceder aos elementos inexistentes vetor[Max - 1] e vetororiginal[Max - 1].


Em principio o memcpy() esta optimizado e é a melhor opcao (em teoria é igualzinho a fazer um loop e copiar um a um).

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.