Busca exponencial
Esta página ou se(c)ção precisa ser formatada para o padrão wiki. (Dezembro de 2017) |
Busca exponencial | |
---|---|
classe | Algoritmo de Busca |
complexidade pior caso | O(log i) |
complexidade caso médio | O(log i) |
complexidade melhor caso | O(1) |
complexidade de espaços pior caso | O(log i) |
espaço | O(1) |
data | Array |
Algoritmos | |
Em ciência da computação, um busca exponencial (também chamado busca a galope ou busca Struzik)[1] é um algoritmo, criado por Jon Bentley e Andrew Chi-Chih Yao em 1976, para a busca listas ordenadas ilimitadas. Existem várias maneiras de se implementar este algoritmo, sendo a mais comum determinar um intervalo em que a chave de pesquisa reside e realizar uma busca binária dentro desse intervalo. Isso leva a uma complexidade O(log i), onde i é a posição da chave de pesquisa na lista, se a chave de pesquisa está na lista, ou a posição onde a chave de pesquisa deve estar, caso a chave de pesquisa não está na lista.
A busca exponencial também pode ser usada para pesquisar em listas limitadas. A busca exponencial pode ainda ser mais rápido que os métodos de busca tradicionais, tais como busca binária, quando o elemento a ser procurado é próximo ao início da lista. A razão para isso é que a busca exponencial será executada em O(log i), onde i é o índice do elemento que está sendo procurado na lista, enquanto que a busca binária tem complexidade de O(log n), onde n é o número de elementos na lista.
Algoritmo[editar | editar código-fonte]
Busca Exponencial permite a pesquisar em uma lista ordenada e sem limites para um determinado valor de entrada (o "valor" a ser buscado na lista). O algoritmo consiste de duas fases. A primeira etapa determina um intervalo em que a chave de pesquisa reside, se existir na lista. Na segunda etapa, uma busca binária é realizada neste intervalo. Na primeira etapa, partindo do princípio que a lista é ordenada de forma ascendente, o algoritmo procura o primeiro expoente, j, onde o valor de 2j é maior do que a chave de pesquisa. Este valor, 2j, torna-se o limite superior para a busca binária com a potência de 2 anterior, 2j - 1, sendo este o limite inferior para a busca binária. Em cada passo, o algoritmo compara o valor da chave de pesquisa com o valor da chave no atual índice de pesquisa. Se o elemento no índice atual é menor do que a chave de busca, o algoritmo repete-se, pulando para o próximo índice de pesquisa, duplicando o índice ao calcular a próxima potência de 2. Se o elemento no índice atual é maior do que a chave de busca, o algoritmo agora sabe que o valor a ser pesquisa está localizado no intervalo formado pelo anterior índice de pesquisa, 2j - 1, e o atual índice de pesquisa, 2j, caso este elemento estiver contido na lista. A busca binária é executada, em seguida. Se a chave não está na lista, a busca binária irá falhar, mas se estiver, a posição da chave na lista é retornada.
Desempenho[editar | editar código-fonte]
A primeira fase do algoritmo leva a um tempo O(log i), onde i é o índice onde a chave de pesquisa estaria na lista. Isso acontece porque ao determinar o limite superior para a pesquisa binária, o loop while é executado exatamente vezes. Já que a lista é ordenada, depois de dobrar o índice de pesquisa vezes, o algoritmo vai realizar uma busca de índice que é maior do que ou igual a i, tal que. Como tal, a primeira fase do algoritmo leva O(log i).
A segunda parte do algoritmo também leva O(log i). Como a segunda fase é simplesmente uma pesquisa binária, leva-se O(log n), onde n é o tamanho do intervalo que está sendo pesquisado. O tamanho deste intervalo seria de 2j - 2j - 1 onde, como visto acima, j = log i. Isto significa que o tamanho do intervalo que está sendo pesquisado é de 2log i - 2log i - 1 = 2log i - 1. Isso resulta em um tempo de execução de log (2log i - 1) = log (i) - 1 = O(log i).
Desta forma, o tempo total de execução do algoritmo, calculado pela soma dos tempos de execução de duas etapas, de O(log i) + O(log i) = 2 O(log i) = O(log i).
Alternativas[editar | editar código-fonte]
Bentley e Yao sugeriram várias variações para busca exponencial. Essas variações consistem em realizar uma pesquisa binária, em oposição a uma busca unária, ao determinar o limite superior para a busca binária na segunda etapa do algoritmo. Isso divide a primeira etapa do algoritmo em duas partes, tornando o algoritmo um algoritmo de três estágios em geral. O novo primeiro estágio determina um valor , bem como antes, de modo que seja maior do que a tecla de pesquisa e é menor do que a chave de busca. Anteriormente, foi determinado de forma unária calculando a próxima potência de 2 (isto é, adicionando 1 a j). Na variação, propõe-se que seja duplicado em vez disso (por exemplo, saltando de 22 para 24 em oposição a 23). O primeiro tal que é maior que a chave de busca um limite superior muito mais difícil do que antes. Uma vez que é encontrado, o algoritmo move-se para o segundo estágio e uma busca binária é realizada no intervalo formado por e dando o expoente do limite superior mais preciso j. A partir daqui, a terceira etapa do algoritmo realiza a busca binária no intervalo 2j - 1 and 2j, como antes. O desempenho desta variação é = O(log i).
Bentley e Yao generalizam esta variação onde de qualquer número k, de buscas binárias é realizada durante a primeira fase do algoritmo, resultando na variante de busca binárias k-aninhada (k-nested binary search). O tempo de execução não se altera para as variações, sendo executado em O(log i), como com o original exponencial algoritmo de pesquisa.
Além disso, uma estrutura de dados com um versão mais apertada da propriedade das árvores spray pode ser dada quando o resultado acima do pesquisa binária k-aninhada é usada em um array ordenado. Assim, o número de comparações feitas durante uma busca é igual a log (d) + log log (d) + ... + S(log *d), onde d é a diferença de pontuação entre o último elemento que foi acessado e o elemento atual sendo acessada.
Veja também[editar | editar código-fonte]
- Busca Linear
- Busca binária
- Interpolação de pesquisa
- Busca Ternária
- Tabela de Hash
Bibliografia[editar | editar código-fonte]
- Bentley, Jon L.; Yao, Andrew C. (1976). «An almost optimal algorithm for unbounded searching». Information Processing Letters. 5 (3): 82–87. ISSN 0020-0190. doi:10.1016/0020-0190(76)90071-5
- Jonsson, Håkan (19 de abril de 2011). «Exponential Binary Search». Consultado em 24 de março de 2014
- Andersson, Arne; Thorup, Mikkel (2007). «Dynamic ordered sets with exponential search trees». Journal of the ACM. 54 (3). 13 páginas. ISSN 0004-5411. doi:10.1145/1236457.1236460
Referências
- ↑ Baeza-Yates, Ricardo; Salinger, Alejandro (2010), «Fast intersection algorithms for sorted sequences», in: Elomaa, Tapio; Mannila, Heikki; Orponen, Pekka, Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday, ISBN 9783642124754, Lecture Notes in Computer Science, 6060, Springer, pp. 45–61, doi:10.1007/978-3-642-12476-1_3.