Obter tempo de execução em milisegundos

[AdSoNaTuRaL]

Galera! 

 

To com um problema, tenho o seguinte código do problema da mochila binária em programação dinâmica e tenho que contar o tempo de execução desse algoritmo.

 

O código é esse:

// Uma solução baseada em programação dinâmica para o problema da mochila binária
#include<stdio.h>
#include<time.h>

// Uma função util que retorna o maximo de dois inteiros
int max(int a, int b) { return (a > b)? a : b; }

// Retorna o valor máximo que pode ser colocado em uma mochila de capacidade W
int Mochila(int cap_mochila, int peso[], int val[], int n)
{

   int i, w;
   int K[n+1][cap_mochila+1];

   
   // Constoi a tabela K[][] de forma bottom up
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= cap_mochila; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (peso[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-peso[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }

   return K[n][cap_mochila];
}

int main()
{

    int val[] = {60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120,
	60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120,
	60, 100, 120};
    int peso[] = {10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30,
	10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30};
    int  cap_mochila = 500;
    int n = sizeof(val)/sizeof(val[0]);
    printf("Maximo inserido na mochila: %d\n", Mochila(cap_mochila, peso, val, n));
    return 0;

}

Alguém poderia me dar uma mão. Eu sei que tenho que usar a biblioteca <time.h>, mas não sei quais os lugares corretos para colocar os parâmetros de iniciar e finalizar a contagem de tempo e de como exibir o resultado com um printf, no main.

[1freakday]

@AdSoNaTuRaL Boa noite, então, acredito que o tempo de execução é sempre a ultima informação a ser 'mostrada' ao usuário, portanto, o printf ficaria antes de return 0; da função main. E no inicio da função main, você iniciaria a contagem da biblioteca time.h.

 

Segue minha versão:

#include <stdio.h>//io
#include <stdlib.h>//system
#include <sys/time.h>//time

//(fim*x+ms) - (inicio*x+ms) = tempo
#define GET_MS(ini, fim)  ((fim.tv_sec * 1000000 + fim.tv_usec) \
			- (ini.tv_sec * 1000000 + ini.tv_usec))

struct timeval inicio, fim;

int main(){
  //Aqui inicia a contagem
  gettimeofday(&inicio, NULL);
  
  
  //Codigo qualquer....
  system("pause");

  
  //Obtem tempo final
  gettimeofday(&fim, NULL);
  
  
  //Fim de execução
  printf("Tempo de execução: %ld ms\n\n", GET_MS(inicio, fim));
  return 0;
}

Perceba que é multiplicado por 1000000, para alcançar os segundos. 

Se você compilar e comparar o tempo de execução com o do compilador, o compilador terá um tempo maior, pois ele conta desde a inicialização, até o encerramento do programa, aqui só conta depois que é executado o gettimeofday inicial, e termina com o gettimeofday final.