Por que a pesquisa binária é mais rápida que a pesquisa ternária?

A pesquisa de uma matriz de elementos usando a pesquisa binária leva, na pior das hipóteses, iterações porque, a cada passo, reduzimos metade do nosso espaço de pesquisa. Se, em vez disso, utilizássemos 'pesquisa ternária', dois terços do nosso espaço de pesquisa a cada iteração; portanto, o pior caso levar iterações ... $N$ $\log_2 N$ $\log_3 N < \log_2 N$

Parece que a pesquisa ternária é mais rápida, então por que usamos a pesquisa binária?

algorithms algorithm-analysis runtime-analysis search-algorithms binary-search The Mean Square
fonte

Não se pode usar o mesmo raciocínio sobre a pesquisa no Quaternário? Ou mesmo busca decimal ... ou qualquer coisa maior do que 2.

d'alar'cop

leia sobre B + Trees

arunmoezhi

A pesquisa linear geralmente é mais rápida que a pesquisa binária em problemas de tamanho pequeno a médio no hardware moderno, porque é coerente com o cache e quase todas as ramificações são previstas corretamente.

Pseudônimo

Também 2 * log_3 (N) = log_3 (N ^ 2) se ele falar com a sua intuição.

PawelP

Vamos colocar isso em termos intuitivos. Se o uso de uma pesquisa baseada em 3 for mais rápido, pois reduz mais o espaço de pesquisa a cada iteração, não será mais rápida a pesquisa baseada em um milhão? Mas você pode ver facilmente que, em média, seria necessário fazer 500.000 verificações dentro de cada iteração para determinar a fatia de milionésima parte do alvo. Claramente, cortar o espaço de pesquisa pela metade a cada iteração e não mais, fornece o máximo de informações em uma única etapa, de maneira confiável.

ErikE 10/09

Respostas:

Se você aplicar a pesquisa binária, você terá muitas comparações. Se você aplicar a pesquisa ternária, terá muitas comparações, pois em cada etapa, será necessário realizar 2 comparações para reduzir o espaço da pesquisa em três partes. Agora, se você fizer as contas, poderá observar que: Como sabemos que , na verdade temos mais comparações com a pesquisa ternária.

\log_{2} (n) + O (1)

$\log_2(n)+O(1)$

2 \cdot \log_{3} (n) + O (1)

$2 \cdot \log_3(n) + O(1)$

2 \cdot \log_{3} (n) + O (1) = 2 \cdot \frac{\log (2)}{\log (3)} \log_{2} (n) + O (1)

$2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1)$

2 \cdot \frac{\log (2)}{\log (3)} > 1

$2 \cdot \frac{\log(2)}{\log(3)} > 1$

A propósito: a pesquisa -ary pode fazer muito sentido, se as comparações forem bastante caras e puderem ser paralelizadas, como então, computadores paralelos podem ser aplicados. $n$

Observe que o argumento pode ser generalizado para arary search com bastante facilidade. Você só precisa mostrar que a função é estritamente monótona aumentando para valores inteiros de . $n$ $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ $k$

DCTLib
fonte

E LHS é linear e RHS é logarítmica, por isso não vai ajudar para qualquer quaternário ou algo mais do que isso .... explicações agradáveis .... Graças

A Mean Square

Apenas por uma questão de completude: observe que uma medida abstrata como o número de comparações de elementos pode ou não dominar o tempo de execução real. Em particular, talvez seja necessário considerar quantas falhas de cache você provavelmente obterá em matrizes longas com qualquer pesquisa. (Aqui, eles coincidem. Estou apenas observando isso porque o OP pergunta: "por que é mais rápido?", E responder que com uma medida abstrata pode ser enganosa para alguns algoritmos.)

Raphael

Em uma pesquisa ternária, 1/3 do tempo você precisará apenas de 1 comparação (faça uma comparação mais baixa: se no terço inferior, você não precisa da segunda comparação). Isso torna o ternário apenas cerca de 5% mais lento em vez de 25% (neste mundo em que nos preocupamos apenas com a contagem de comparação). Não sei como generalizar isso para o n-ário, embora eu suspeite que nunca seja mais rápido que o binário.

Aaron Dufour

@AaronDufour: Como se poderia fazer uma pesquisa quaternária comparando primeiro com o item do meio e depois ignorando o resultado das outras comparações, a única maneira pela qual a pesquisa quaternária poderia ser mais rápida seria se três comparações pudessem ser feitas em paralelo mais barato do que duas comparações. pode ser realizado sequencialmente.

supercat

@AaronDufour Mas você está se amortizando com os elementos a serem pesquisados, e não está claro para mim por que está tudo bem. No pior dos casos, ambas as comparações podem ser realizadas a cada etapa.

Sasho Nikolov

O DCTLib está certo, mas esqueça a matemática por um segundo.

Pela sua lógica então, n- ar deve ser o mais rápido. Mas se você pensar bem, n- ar é exatamente igual a uma pesquisa de iteração regular (apenas iterando pela lista 1 por 1, mas na ordem inversa). Primeiro, você seleciona o último item (ou o penúltimo) na lista e compara esse valor ao seu valor de comparação. Em seguida, você remove esse item da sua lista e escolhe o último item na nova lista, que é apenas o penúltimo valor da matriz. Cada vez, você eliminaria apenas 1 valor por vez até encontrar seu valor.

Em vez disso, você deve pensar assim - como faço para eliminar o máximo de valores da lista a cada iteração? Em uma pesquisa binária, você sempre elimina metade da lista. Em uma pesquisa ternária, existe a possibilidade (33,33% de chance, na verdade) de você eliminar 2/3 da lista, mas há uma chance ainda maior (66,66%) de eliminar apenas 1/3 da lista. para calcular O (n), você precisa observar o pior cenário, que é 1/3, menor que 1/2. À medida que você se aproxima cada vez mais de n, fica ainda pior.

Não apenas o pior cenário será aprimorado com a pesquisa binária, mas também o tempo médio . Observando o valor esperado (que parte da lista podemos remover em média), usamos esta fórmula:

(P_lower) x (parte que podemos remover se for menor) + (P_higher) x (parte que podemos remover se for maior) = E

Para pesquisa binária, isso é .5x.5 + .5x.5 = .5 (sempre removemos metade da lista). Para pesquisas ternárias, esse valor é .666x.333 + .333x.666 = 0.44, ou a cada etapa, provavelmente removeremos apenas 44% da lista, tornando-a menos eficiente que a pesquisa binária, em média. Esse valor atinge o pico em 1/2 (metade da lista) e diminui quanto mais você chegar a n (iteração reversa) e 0 (iteração regular).

Ok, então eu menti .. há um pouco de matemática envolvida, mas espero que ajude!

dberm22
fonte

Esta é uma ótima resposta.

The_Sympathizer

Ya análise de limites ajuda a entender matemática difícil! A pesquisa seqüencial n-ária tem o mesmo custo da pesquisa linear O (n).

shuva 26/10/18

-2

Observe que o argumento das comparações log (N) vs 2 log (N) é baseado em uma interpretação ingênua do algoritmo. Se eu realmente sentasse e escrevesse isso na montagem x86, os resultados seriam invertidos. O problema é o uso de números inteiros para casos de teste combinados com um compilador insuficientemente inteligente que não pode remover as comparações redundantes. Tente novamente com strings e uma função de comparação de strings apropriada e codifique-a para chamar a função de comparação uma vez por loop e você descobrirá que a pesquisa ternária é mais rápida novamente.

Joshua
fonte

É claro que a pesquisa ternária seria mais rápida se você pudesse fazer isso com apenas uma comparação por iteração. Mas, não importa se strings ou números inteiros, você não pode.

FrankW

As comparações não seriam redundantes e o problema não tem nada a ver com o compilador. Para dividir o espaço de pesquisa em três partes, você precisa de 2 comparações. Em uma pesquisa binária, você precisa apenas comparar com o elemento do meio e saber em qual metade do espaço de pesquisa o resultado estaria. Com a pesquisa ternária, você precisaria comparar com o elemento 1/3 do caminho list E o 2/3 do caminho através da lista. Que tipo de dados você está comparando ou qual idioma está usando é irrelevante. Concedido, se o item estiver no 1º 3º, você poderá parar após 1 comparação.

reirab 9/09/14

Em algumas plataformas, a pesquisa ternária pode ser mais rápida, pois permite que a CPU obtenha mais tempo para buscar os operandos da RAM antes de precisar deles para comparação. Mas isso depende totalmente da plataforma usada e de suas latências e caches.

jpa

Droga - definição incorreta de pesquisa ternária.

Joshua