Algoritmos e complexidade

Procuramos 14 em [2, 5, 8, 11, 14, 17, 20]; podemos visitar os valores desde o início ou usar a ordenação para excluir metade dos candidatos. O contrato deve dizer se queremos uma posição qualquer ou a primeira ocorrência, e como representar a ausência.

Pesquisa linear e pesquisa binária

A pesquisa linear visita os elementos por ordem até encontrar o alvo; escolhemos neste exemplo devolver um índice, ou None quando o alvo falta, convenção que evita confundir ausência com o índice zero.

A pesquisa binária exige uma lista ordenada. Mantém um intervalo de candidatos, compara com o meio e conserva só a metade possível.

def linear(valores, alvo):
    for i, valor in enumerate(valores):
        if valor == alvo:
            return i
    return None

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

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

A condição inicio <= fim inclui o último candidato, e atualizar para meio - 1 ou meio + 1 exclui o meio já comparado para garantir progresso.

Se o alvo faltar, o intervalo torna-se vazio. A ordenação é a razão para descartar cada metade, e numa lista desordenada essa decisão pode perder o alvo.

Com valores repetidos, esta função pode devolver qualquer posição com o alvo. Se o contrato pede a primeira, encontrar uma ocorrência ainda não chega; tens de continuar à esquerda ou usar outra estratégia.

Contar operações

Conta primeiro num caso concreto: com 7 elementos, a pesquisa linear pode fazer 7 comparações; a binária do exemplo encontra 14 em 3 iterações. Se n é o comprimento da lista, a pesquisa linear faz até n comparações de igualdade. A binária reduz o número de candidatos aproximadamente a metade por iteração, fazendo um número de iterações proporcional a $\log_2 n$.

A notação $O(g(n))$ é um limite superior do crescimento do trabalho para entradas suficientemente grandes. Por exemplo, $3n+2$ é $O(n)$: a partir de $n=1$, nunca ultrapassa $5n$. Também é $O(n^2)$, mas esse limite é menos informativo. Para exprimir um limite superior e inferior da mesma ordem, usa-se $\Theta$; $3n+2$ é $\Theta(n)$. Dizer apenas $O(n^2)$ não prova que um algoritmo precise de trabalho quadrático.

Esta análise é um complemento para comparar estratégias. O tamanho da entrada e a operação contada têm de estar definidos. Os inteiros Python podem ter tamanho arbitrário; tratar qualquer operação aritmética como constante é uma simplificação que exige valores de tamanho limitado.

Ciclos sucessivos e aninhados

Dois percursos sucessivos de n elementos fazem trabalho proporcional a $2n$, portanto linear, enquanto dois percursos aninhados, ambos de n, fazem $n^2$ visitas. Não é o número de ciclos escritos que decide o custo, é quantas vezes o corpo executa.

n = 4
pares = 0
for i in range(n):
    for j in range(i + 1, n):
        pares += 1
print(pares)

A saída é 6: para i = 0, visitamos j = 1, 2, 3; para i = 1, visitamos j = 2, 3; para i = 2, só j = 3; para i = 3, não há parceiros. As visitas são $3+2+1+0=6$ e, em geral, somamos $(n-1)+(n-2)+\cdots+1=n(n-1)/2$, logo o crescimento é quadrático embora o ciclo interior não percorra sempre n posições.

Custos das operações mais usadas

Uma fatia de k elementos de lista cria outra lista e custa trabalho proporcional a k. Inserir no início desloca elementos. append tem custo amortizado constante.

Para uma única procura, ordenar primeiro costuma acrescentar trabalho desnecessário. Para muitas procuras sobre a mesma lista, a preparação pode compensar.

Uma medição em segundos compara uma implementação e um ambiente; a análise de crescimento explica o que muda quando a entrada aumenta. Nenhuma destas medidas substitui a prova de que a resposta está correta.

Para aprofundar invariantes de ciclos e crescimento do trabalho, tens este complemento opcional de Rodrigo Dias:

Invariantes e Análise Assintótica 101Carregar vídeo do YouTube

Abrir no YouTube