Ao comparar um conjunto de soluções (i.e., algoritmos) para um mesmo problema, pode-se desejar analisar qual das soluções é mais eficiente. Geralmente analisa-se a eficiência de um algoritmo em termos do tempo e espaço necessários para se obter a solução para uma entrada de cardinalidade N. Esta análise pode levar em consideração o melhor caso, caso médio e o pior caso, sendo este último de importância fundamental porque oferece uma garantia que o algoritmo não exigirá mais tempo do que o estimado para quaisquer combinações possíveis para uma entrada de cardinalidade N.

Tarefa:

Comparar o tempo de execucao dos modos de consulta sequencial e consulta binária.

Entrada: Gerar aleatoriamente dez mil (10.000) valores inteiros positivos e distintos armazenando-os em um vetor (i.e., array) em ordem crescente. Para gerar os valores inteiros, utilize a classe Random (veja detalhes abaixo).

Saída: Para cada um dos métodos de consulta, executar trinta (30) rodadas do seguinte experimento: gerar aleatoriamente dez mil (10.000) valores inteiros executando a consulta de cada um dos valores no vetor de entrada. Apresentar como saída o valor médio das 30 medidas para cada um dos métodos.

Métodos Úteis:

System.nanoTime() 

System.currentTimeMillis()

• Para gerar numeros pseudo-randomicos:

Random (do pacote java.util.Random);

Random(semente);

Random.nextInt() 

Obs.: Mais informações sobre geração de números pseudo-randômicos em Random Numbers in Java