Exemplos - Análise de Algoritmos

Exemplos.java

package aula3;

import java.util.Random;

class Exemplos {

    public static void main(String[] args) {
        int[] valores;
        boolean encontrado;

        // log2(8) = 3
        valores = criarVetorAscendente(8);
        iniciarMedicao("Busca Binária com 8 elementos");
        encontrado = buscaBinaria(valores, -1);
        encerrarMedicao();
        System.out.println("Encontrado: " + encontrado);

        // log2(16) = 4
        valores = criarVetorAscendente(16);
        iniciarMedicao("Busca Binária com 16 elementos");
        encontrado = buscaBinaria(valores, -1);
        encerrarMedicao();
        System.out.println("Encontrado: " + encontrado);

        // log2(32) = 5
        valores = criarVetorAscendente(32);
        iniciarMedicao("Busca Binária com 32 elementos");
        encontrado = buscaBinaria(valores, -1);
        encerrarMedicao();
        System.out.println("Encontrado: " + encontrado);
        
    }

    /**
     * Complexidade de Tempo = O(log(n))
     */
    public static boolean buscaBinaria(int[] valores, int valorProcurado) {
     // Esquerda = 0
     // Direita = N
     // Meio = Esquerda + (Direita - Esquerda) / 2
     int esquerda = 0;
     int direita = valores.length - 1;
     while (esquerda <= direita) {
         contarIteracao();
         int meio = esquerda + (direita - esquerda) / 2;
         if (valores[meio] == valorProcurado) {
             return true;
         }
         if (valorProcurado < valores[meio]) {
            direita = meio - 1;
         } else {
            esquerda = meio + 1;
         }
     }
     return false;
    }

    /**
     * Complexidade de Tempo = O(n)
     */
    public static boolean buscarValor(int[] valores, int valorProcurado) {
        for (int i = 0; i < valores.length; i++) {
            contarIteracao();
            if (valores[i] == valorProcurado) {
                return true;
            }
        }
        return false;
    }

    /** 
     * Complexidade de Tempo = O(1)
    */
    public static int obterPrimeiroElemento(int[] valores) {
        contarIteracao();
        return valores[0];
    }

    /**
     * Os métodos e propriedades abaixo auxiliam na criação de vetores e na
     * medição do tempo de execução / número de iterações.
     */

    static boolean medindo = false;
    static long iteracoes = 0;
    static long inicio = 0;
    static String descricao = "";

    public static int[] criarVetorAscendente(int comprimento) {
        int[] valores = new int[comprimento];
        for (int i = 0; i < valores.length; i++) {
            valores[i] = i;
        }
        return valores;
    }

    public static int[] criarVetorDescendente(int comprimento) {
        int[] valores = new int[comprimento];
        for (int i = 0; i < valores.length; i++) {
            valores[i] = valores.length - i;
        }
        return valores;
    }

    public static int[] criarVetorAleatorio(int comprimento) {
        int[] valores = new int[comprimento];
        Random r = new Random(0);
        for (int i = 0; i < valores.length; i++) {
            valores[i] = r.nextInt() % 100;
        }
        return valores;
    }

    public static void iniciarMedicao() {
        Exemplos.iniciarMedicao("");
    }

    public static void iniciarMedicao(String descricao) {
        if (medindo) {
            System.out.println("Você deve encerrar a medição anterior antes de iniciar uma nova medição.");
            return;
        }
        Exemplos.descricao = descricao;
        Exemplos.medindo = true;
        Exemplos.iteracoes = 0;
        Exemplos.inicio = System.nanoTime();
    }

    public static void contarIteracao() {
        iteracoes++;
    }

    public static void encerrarMedicao() {
        long fim = System.nanoTime();
        if (!medindo) {
            System.out.println("Você deve iniciar a medição antes de encerrar.");
            return;
        }
        System.out.println("* ------------------------------------ *");
        System.out.println("* Resultado da Medição: " + Exemplos.descricao);
        System.out.println("* Iterações: " + Exemplos.iteracoes);
        System.out.printf("* Tempo de Execução: %f segundos.\n", (double)(fim - Exemplos.inicio) / 1_000_000_000);
        
        inicio = 0;
        iteracoes = 0;
        descricao = "";
        medindo = false;
    }
}