Algoritmos

Busca, ordenação e complexidade

Algoritmos são sequências finitas de passos para resolver um problema. A eficiência é medida pela notação Big O, que descreve como o tempo de execução cresce com o tamanho n da entrada: O(1) constante, O(log n) logarítmico (divide e conquista), O(n) linear, O(n log n) linearítmico (bons sorts), O(n²) quadrático (loops aninhados).

Os algoritmos de busca mais importantes são busca linear O(n) (funciona em qualquer array) e busca binária O(log n) (exige array ordenado, extremamente eficiente). Para ordenação, Java usa internamente Timsort (Arrays.sort, Collections.sort) — O(n log n) no pior caso, estável e muito eficiente em dados parcialmente ordenados.

Os algoritmos recursivos dividem o problema em subproblemas menores do mesmo tipo. Recursão é a base do divide and conquer e de estruturas como árvores. A pilha de chamadas tem limite, então cuidado com recursão muito profunda (StackOverflowError).

Exemplo.java

// ── Busca Linear: O(n) ───────────────────────────
public static int buscaLinear(int[] arr, int alvo) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == alvo) return i;
    }
    return -1; // não encontrado
}

// ── Busca Binária: O(log n) — array ordenado ──────
public static int buscaBinaria(int[] arr, int alvo) {
    int inicio = 0, fim = arr.length - 1;
    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2; // evita overflow
        if (arr[meio] == alvo)  return meio;
        if (arr[meio] < alvo)   inicio = meio + 1;
        else                    fim    = meio - 1;
    }
    return -1;
}

// ── Fibonacci recursivo: O(2^n) vs iterativo: O(n) ─
public static long fibRecursivo(int n) {
    if (n <= 1) return n;
    return fibRecursivo(n - 1) + fibRecursivo(n - 2);  // lento!
}

public static long fibIterativo(int n) {
    if (n <= 1) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) { long t = a + b; a = b; b = t; }
    return b;  // muito mais rápido
}

int[] arr = {3, 7, 12, 18, 25, 31, 45};
System.out.println(buscaBinaria(arr, 18)); // 3

💡 Dica pro

Para entrevistas técnicas: domine busca binária, recursão, e as complexidades de List/Map/Set. São os mais cobrados. Sempre analise: "qual o Big O desse trecho?"

Recompensa+50 XP+exercícios