In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are numerous ways to implement this with the most common being to determine a range that the search key resides in and performing a binary search within that range. This takes O(log i) where i is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Búsqueda exponencial (es)
- Exponential search (en)
- Busca exponencial (pt)
|
| rdfs:comment
| - In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are numerous ways to implement this with the most common being to determine a range that the search key resides in and performing a binary search within that range. This takes O(log i) where i is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list. (en)
- En Ciencias de la Computación, una búsqueda exponencial (también llamado búsqueda galopante o búsqueda Struzik) es un algoritmo, creado por Jon Bentley y Andrew Chi-Chih Yao en 1976, para buscar en listas infinitas/no acotadas ordenadas. Hay numerosas maneras para implementarlo siendo la más común determinar el rango en que la llave de búsqueda reside y realizar una búsqueda binaria dentro de dicho rango. Esto demora O(log i) dónde i es la posición de la llave de búsqueda en la lista, si la llave de búsqueda está en la lista, o la posición donde la llave de búsqueda debería estar, si la llave de búsqueda no está en la lista. (es)
- Em ciência da computação, um busca exponencial (também chamado busca a galope ou busca Struzik) é 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. (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| space
| |
| dbp:wikiPageUsesTemplate
| |
| class
| |
| data
| |
| time
| |
| has abstract
| - In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are numerous ways to implement this with the most common being to determine a range that the search key resides in and performing a binary search within that range. This takes O(log i) where i is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list. Exponential search can also be used to search in bounded lists. Exponential search can even out-perform more traditional searches for bounded lists, such as binary search, when the element being searched for is near the beginning of the array. This is because exponential search will run in O(log i) time, where i is the index of the element being searched for in the list, whereas binary search would run in O(log n) time, where n is the number of elements in the list. (en)
- En Ciencias de la Computación, una búsqueda exponencial (también llamado búsqueda galopante o búsqueda Struzik) es un algoritmo, creado por Jon Bentley y Andrew Chi-Chih Yao en 1976, para buscar en listas infinitas/no acotadas ordenadas. Hay numerosas maneras para implementarlo siendo la más común determinar el rango en que la llave de búsqueda reside y realizar una búsqueda binaria dentro de dicho rango. Esto demora O(log i) dónde i es la posición de la llave de búsqueda en la lista, si la llave de búsqueda está en la lista, o la posición donde la llave de búsqueda debería estar, si la llave de búsqueda no está en la lista. La búsqueda exponencial también puede ser usada en listas acotadas. La búsqueda exponencial puede incluso mejorar los tiempos de algoritmos de búsqueda en listas acotadas, como búsqueda binaria, cuando el elemento buscado está cerca del principio del array. Esto es porque la búsqueda exponencial correrá en O(log i), donde i es el índice del elemento buscado en la lista, mientras que la búsqueda binaria correría en O(log n), donde n es el número de elementos en la lista. (es)
- Em ciência da computação, um busca exponencial (também chamado busca a galope ou busca Struzik) é 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. (pt)
|
| average-time
| |
| best-time
| |
| optimal
| |
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)