Exemplos Práticos de Complexidade de Algoritmos com Java
1. Busca Linear (O(n))
A busca linear verifica cada elemento de uma lista até encontrar o alvo.
Exemplo:
- Lista: [2, 4, 6, 8, 10]
- Alvo: 8
Passos do teste de mesa:
| Índice | Valor | Comparação (Alvo = 8)? | Ação |
|--------|-------|------------------------|------------|
|0 | 2 | Não | Próximo |
|1 | 4 | Não | Próximo |
|2 | 6 | Não | Próximo |
|3 | 8 | Sim | Encontrado |
Código Java:
public class BuscaLinear {
public static int buscaLinear(int[] arr, int alvo) {
for (int i = 0; i < [Link]; i++) {
if (arr[i] == alvo) return i;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10};
int alvo = 8;
int resultado = buscaLinear(arr, alvo);
[Link]("Índice do alvo: " + resultado);
}
}
2. Busca Binária (O(log n))
A busca binária divide a lista ao meio repetidamente até encontrar o alvo.
Exemplo:
- Lista: [2, 4, 6, 8, 10]
- Alvo: 8
Passos do teste de mesa:
1. (0, 4) -> meio = 2 -> 6 -> menor que 8 -> novo início = 3
2. (3, 4) -> meio = 3 -> 8 -> igual ao alvo
Código Java:
public class BuscaBinaria {
public static int buscaBinaria(int[] arr, int alvo) {
Exemplos Práticos de Complexidade de Algoritmos com Java
int inicio = 0, fim = [Link] - 1;
while (inicio <= fim) {
int meio = (inicio + fim) / 2;
if (arr[meio] == alvo) return meio;
else if (arr[meio] < alvo) inicio = meio + 1;
else fim = meio - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10};
int alvo = 8;
int resultado = buscaBinaria(arr, alvo);
[Link]("Índice do alvo: " + resultado);
}
}
3. Ordenação por Bolha (O(n²))
A ordenação por bolha compara e troca elementos vizinhos se estiverem fora de ordem.
Exemplo:
Lista inicial: [5, 3, 8, 4, 2]
Lista ordenada: [2, 3, 4, 5, 8]
Código Java:
public class OrdenacaoBolha {
public static void ordenacaoBolha(int[] arr) {
int n = [Link];
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
ordenacaoBolha(arr);
for (int i : arr) [Link](i + " ");
}
}
4. Ordenação por Fusão (O(n log n))
Exemplos Práticos de Complexidade de Algoritmos com Java
Divide a lista em partes menores, ordena e mescla de volta.
Exemplo:
Lista inicial: [5, 3, 8, 4, 2]
Lista ordenada: [2, 3, 4, 5, 8]
Código Java:
public class OrdenacaoFusao {
public static void mergeSort(int[] arr) {
if ([Link] <= 1) return;
int meio = [Link] / 2;
int[] esquerda = new int[meio];
int[] direita = new int[[Link] - meio];
[Link](arr, 0, esquerda, 0, meio);
[Link](arr, meio, direita, 0, [Link] - meio);
mergeSort(esquerda);
mergeSort(direita);
merge(arr, esquerda, direita);
}
public static void merge(int[] arr, int[] esq, int[] dir) {
int i = 0, j = 0, k = 0;
while (i < [Link] && j < [Link]) {
arr[k++] = esq[i] <= dir[j] ? esq[i++] : dir[j++];
}
while (i < [Link]) arr[k++] = esq[i++];
while (j < [Link]) arr[k++] = dir[j++];
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
mergeSort(arr);
for (int i : arr) [Link](i + " ");
}
}