Neste post, vamos implementar em Java e descrever indutivamente um algoritmo que realiza a busca sequencial em um vetor. Apresentaremos uma implementação recursiva, em outro post trataremos da implementação iterativa.
Descrição indutiva:
- Caso Base: Trivial, não fazemos busca em listas vazias.
- Hipótese de Indução: Vamos supor que a hipótese de indução busca um valor em uma lista com n-1 elementos.
- Caso Geral: Simples, verificamos se o último elemento é o valor procurado, se não for entregamos os n-1 primeiros elementos para a hipótese de indução que se encarrega de fazer a busca no resto da lista.
Agora, apresentaremos uma implementação que decorre da descrição indutiva apresentada acima.
- Implementação em Java:
public class LinearSearch { public static int linearSearch(int vet[], int n, int value) { if (n >= 0) { if (vet[n] == value) return n; else return linearSearch(vet, n - 1, value); } return -1; } public static void main(String[] args) { int vet[] = { 10, 2, 43, 14, 25, 6, 37 }; int value = 14; int index = linearSearch(vet, 6, value); if (index == -1) System.out.println("Elemento não encontrado"); else System.out.println("O índice do elemento " + value + " é: " + index); } }Complexidade do algoritmo/implementação:
Usando indução não é difícil encontrar uma relação de recorrência que expresse o tempo de execução do algoritmo acima. O raciocínio é simples, basta imaginar que o tempo total do algoritmo é o tempo que gastamos para verificar se o último elemento é o procurado, mais o tempo que a hipótese de indução gastou para procurar nos n-1 elementos restantes, ou seja, T(n) = T(n-1) + O(1). Resolvendo a recorrência, temos
T(n) = T(n-1) + O(1)
T(n) = T(n-2) + 1 + 1
T(n) = T(n-3) + 1 + 1 + 1
T(n) = T(n-4) + 1 + 1 + 1 + 1 + 1
...
T(n) = T(0) + 1 + 1 + 1 + ... + 1
T(n) = O(n)
Analisando a relação de recorrência, podemos perceber que a busca sequencial possui complexidade linear, o algoritmo visita cada elemento apenas uma vez.
Seguir @inductioncode
Nenhum comentário:
Postar um comentário