Análise do algoritmo de busca linear §

---

A busca linear é um algoritmo simples que visa encontrar um valor específico (x) em um vetor de inteiros (v).

O problema é determinar um índice tal que , ou seja, o índice onde o valor se encontra no vetor. Caso o valor não esteja presente, o algoritmo retorna -1.

Funcionamento Básico §

O algoritmo percorre o vetor elemento por elemento, verificando se o valor é igual ao valor do vetor naquela posição. A busca ocorre da primeira até a última posição do vetor, ou seja, é uma busca sequencial.

Algoritmo §

busca-linear(v, n, x)    cost   times
	para k = 1 até n     (c1)   n + 1
		se v[k] == x     (c2)   n
			retorne k    (c3)   1
		fim se
	retorne −1           (c4)   1

Análise de Complexidade §

• Melhor Caso: O elemento é encontrado na primeira posição do vetor. Nesse cenário, o algoritmo realiza apenas uma iteração, verificando a primeira posição, o que resulta em tempo constante, .

• Pior Caso: O elemento está na última posição do vetor, ou não está presente. Nesse caso, o algoritmo percorre todas as posições do vetor, tornando a execução linear, .

Referências §

---

Aula 2 - Análise de algoritmos