Comparações médias na busca linear

Sob a hipótese padrão de que o alvo tem a mesma chance de ocupar qualquer posição, ela informa tanto o número esperado de comparações quanto o pior caso. Assim, desenvolvedores, estudantes e revisores podem relacionar a notação O(n) a contagens concretas para um tamanho específico de coleção.

Entenda o modelo de probabilidade por trás da média

A busca linear examina os elementos em ordem e para assim que encontra o alvo. Se um alvo presente tiver a mesma probabilidade de ocupar qualquer uma das n posições, encontrar o primeiro elemento custa uma comparação, o segundo custa duas e o último custa n. Cada custo tem probabilidade 1/n. Portanto, o custo esperado é a média aritmética dos inteiros de 1 até n, simplificada para (n + 1) / 2. Informe o tamanho da coleção como n e a calculadora aplicará exatamente essa fórmula. A hipótese é essencial: isto não é uma estimativa baseada em tempo, hardware ou linguagem de programação. É uma contagem determinística para uma busca bem-sucedida com distribuição uniforme das posições. Se algumas posições ou valores forem procurados com maior frequência, as probabilidades deverão ser ponderadas separadamente. O modelo também não representa um alvo ausente, situação em que a busca linear comum sempre examina todos os n elementos.

Interprete as comparações médias e de pior caso

O resultado médio pode ser inteiro ou terminar em meio ponto. Por exemplo, uma coleção com 100 elementos tem custo esperado de 50.5 comparações. Esse valor fracionário não significa que uma execução faça meia comparação; ele é a média de longo prazo de muitas buscas bem-sucedidas com posições uniformes. O pior caso é n, pois um alvo na última posição só aparece depois que todos os elementos forem verificados. Em uma coleção de um elemento, ambos os valores são um. Conforme n cresce, a média se aproxima da metade do tamanho, enquanto o pior caso continua igual ao tamanho total. As duas grandezas crescem linearmente, por isso a análise assintótica classifica a busca linear bem-sucedida como O(n), apesar das constantes diferentes. Use a média para uma carga que realmente siga a distribuição informada e o pior caso como limite rígido para uma consulta bem-sucedida. A contagem não inclui controle do laço, acesso à memória, ordenação nem a complexidade interna da comparação.

Use o resultado em decisões de projeto e desempenho

Contagens concretas tornam discussões sobre algoritmos mais úteis do que a notação assintótica isolada. Você pode comparar o trabalho esperado da busca linear com o custo de criar outra estrutura de dados, principalmente quando a coleção é pequena, pouco consultada ou muda com frequência. Uma tabela hash ou um índice ordenado pode reduzir o trabalho de consulta, mas sua construção e manutenção têm um custo que uma varredura simples evita. Esta calculadora fornece o lado da varredura sem alegar que mede tempo de execução. Ela também ajuda a conferir exercícios, validar um modelo de planilha, documentar uma revisão de código ou produzir valores estáveis para material didático. Registre as condições junto ao resultado: o alvo está presente, todas as posições são equiprováveis e a busca começa no primeiro elemento e para na primeira correspondência. Duplicatas podem invalidar o modelo porque a primeira ocorrência encerra a busca. Para alvos ausentes, use n comparações; para acessos não uniformes, calcule uma esperança ponderada.