Algoritmos e complexidade

Pesquisa linear e binária

• A pesquisa linear visita elementos por ordem. Devolver no primeiro igual encontra a primeira ocorrência, mesmo numa lista desordenada.
• A pesquisa binária exige uma sequência ordenada e acesso direto ao meio. Compara com o meio e exclui a metade impossível.
• Define o resultado para ausência: aqui usamos None, distinguindo-o do índice zero. Com repetidos, esta pesquisa binária pode devolver qualquer ocorrência.

def binaria(valores, alvo):
    inicio, fim = 0, len(valores) - 1
    while inicio <= fim:
        meio = (inicio + fim) // 2
        if valores[meio] == alvo:
            return meio
        if alvo < valores[meio]:
            fim = meio - 1
        else:
            inicio = meio + 1
    return None

xs = [2, 5, 8, 11, 14, 17, 20]
print(binaria(xs, 14), binaria(xs, 9), binaria([], 2))

A saída é 4 None None: para 14, os meios têm valores 11, 17 e 14.

• inicio <= fim inclui o último candidato; meio ± 1 exclui o meio já rejeitado e garante progresso.
• Ausência termina num intervalo vazio.
• Ordenar antes da pesquisa muda as posições relativamente à entrada original.

Crescimento do trabalho

Define o tamanho n da entrada, a operação contada e o caso analisado.

• $O(g(n))$ é um limite superior para entradas suficientemente grandes; $\Theta(g(n))$ dá também um limite inferior da mesma ordem.
• $3n+2$ é $\Theta(n)$ e também $O(n^2)$; o segundo limite não prova custo quadrático.

• O modelo considera acessos e comparações de valores com custo limitado.
• Aritmética com inteiros Python arbitrariamente grandes não é sempre constante.

Ciclos e operações escondidas

• Dois percursos sucessivos de n elementos somam trabalho linear; dois percursos aninhados completos fazem n² visitas.

• Para pares i < j, as visitas são $n(n-1)/2$: com n = 4, há 6 pares. O crescimento continua quadrático.

• Uma fatia de k elementos copia-os, custando $\Theta(k)$; inserir no início desloca elementos. append tem custo amortizado constante.

• Pertença numa lista pode visitar todos os elementos. Dicionários/conjuntos têm custo médio esperado constante sob hipóteses adequadas sobre hashes, mas pior caso linear.

• Ordenar para uma só procura pode acrescentar trabalho desnecessário; muitas procuras podem compensar a preparação.

• Medir segundos compara implementações num ambiente; analisar crescimento compara o efeito de aumentar a entrada. Nenhum dos dois prova correção.