Complexidade de Algoritmos: Busca Sequencial e Binária

Módulo: Fatores de Método Eficiente

Fatores de método eficiente: Função de complexidade do algoritmo (f(n)), espaço de memória utilizado na ordenação, tamanho do conjunto de dados, ordenação inicial do conjunto de dados.

Sempre que estiver multiplicando é log₂N |X|. Quando for +, a complexidade é divisão.

Complexidade de Algoritmo

Fornece a medida do trabalho envolvido na execução de um determinado algoritmo.

Notação ‘O’ (Big O)

A complexidade de algoritmos só tem sentido para problemas que envolvem uma grande quantidade de dados.

Passos para achar ‘O’

1. Escreva a função que representa a complexidade.
2. Faça cada coeficiente da função igual a 1.
3. Mantenha o maior termo da função e descarte os demais termos.

Categorias de Grandezas

log n, n, n log n, n², n³, n^k, 2ⁿ, n!

Busca Sequencial

Visa procurar o valor através de comparações sucessivas a partir do primeiro elemento (ou último) até que se encontre o valor desejado ou até que os elementos da estrutura se esgotem.

public static int buscaSequencial(double[] vetor, double buscado) {
    int i = 0;
    while (i < vetor.length && vetor[i] != buscado) {
        i++;
    }
    if (i < vetor.length) {
        return i;
    } else {
        return -1;
    }
}

Como é feito:

1. Iniciar pela posição inicial do vetor.
2. Enquanto o número buscado não for encontrado ou não existirem mais números para comparar.
3. Caso o número buscado tenha sido encontrado, retornar sua posição; do contrário, avisar que não foi encontrado.

Melhor caso: F(N) = 1. Pior caso: F(N) = N. Caso médio: F(N) = (N+1) / 2.

Busca Binária

É um algoritmo de busca em vetores que segue o paradigma de divisão e conquista.

public static int buscaBinaria(double[] vetorOrd, double buscado) {
    int ini = 0, fin = vetorOrd.length - 1;
    int med = (ini + fin) / 2;
    while (ini <= fin && vetorOrd[med] != buscado) {
        if (buscado > vetorOrd[med]) {
            ini = med + 1;
        } else {
            fin = med - 1;
        }
        med = (ini + fin) / 2;
    }
    if (ini <= fin) {
        return med;
    } else {
        return -1;
    }
}

Como é feito:

1. Armazenar a posição inicial e a final do vetor.
2. Enquanto o número buscado não for encontrado, é preciso encontrar a posição central do vetor.
3. Caso o número buscado tenha sido encontrado, retornar sua posição; do contrário, avisar que não foi encontrado.

Melhor caso: F(N) = 1. Pior caso: F(N) = log₂ N. Caso médio: F(N) = (1+log₂N).

Cenários Sequencial e Binária – Pior Caso

Maior custo de execução do algoritmo sobre todas as entradas de tamanho n.