Para buscar un elemento dentro de un vector (array) hay que recorrer dicho vector, elemento a elemento, hasta encontrar el elemento en cuestión o hasta que se acabe el vector.
La complejidad de los algoritmos se calcula teniendo en cuenta el peor caso posible. Para el caso de una búsqueda en un vector de tamaño n, el peor caso es que el elemento no se encuentre en el vector, con lo que habría que recorrer los n elementos del vector antes de poder decir que el elemento no se encuentra en el mismo. A la complejidad de esta operación se la denomina de orden lineal (O(n)).
El algoritmo de búsqueda binaria (o búsqueda dicotómica) es un algoritmo de búsqueda en vectores ordenados que permite disminuir la complejidad de la búsqueda en dichos vectores.
La intuición detrás de la búsqueda binaria es la misma que cuando se busca en un diccionario; cuando se va a buscar una palabra que empieza por la letra "s", nadie comienza a leerse las palabras que empiezan por la "a", luego la "b", y así en adelante. Normalmente, se abre el diccionario por la mitad y, dependiendo de si la letra inicial por la que hemos abierto es mayor o menor que la que buscamos, descartamos la mitad de las palabras de la enciclopedia y ya solo buscamos en la mitad restante.
El pseudocódigo del algoritmo de búsqueda binaria se puede encontrar, por ejemplo, aquí. El algoritmo consiste en mantener unos índices que marcan los límites superior e inferior de la parte del vector que nos queda por analizar.
Para calcular la complejidad de este algoritmo, inicialmente en número de elementos por analizar es n. Tras la primera división, el número será como mucho n/2 (pues nos hemos quedado con la mitad de elementos); tras la segunda división, el número será como mucho n/4; y así sucesivamente. Por lo general, tras la división número i, el número de elementos por analizar será como mucho:
El peor caso se da cuando el elemento a buscar no se encuentra en el vector (es decir, cuando tras dividir los elementos por analizar nos quedemos con un número menor a 1). Por lo tanto, el número máximo de llamadas a realizar es el menor número m tal que:
Transformando esta fórmula a un logaritmo en base 2, tenemos que:
y que
es decir, que el número m depende, no del tamaño n del vector, sino del logaritmo de dicho n.
Es por esto que el algoritmo de búsqueda binaria tiene una complejidad de orden logarítmico (O(log n)).
Referencia:
Michael T. Goodrich y Roberto Tamassia. Data Structures and Algorithms in Java, Fifth edition. John Wiley & Sons. 2011.
La complejidad de los algoritmos se calcula teniendo en cuenta el peor caso posible. Para el caso de una búsqueda en un vector de tamaño n, el peor caso es que el elemento no se encuentre en el vector, con lo que habría que recorrer los n elementos del vector antes de poder decir que el elemento no se encuentra en el mismo. A la complejidad de esta operación se la denomina de orden lineal (O(n)).
El algoritmo de búsqueda binaria (o búsqueda dicotómica) es un algoritmo de búsqueda en vectores ordenados que permite disminuir la complejidad de la búsqueda en dichos vectores.
La intuición detrás de la búsqueda binaria es la misma que cuando se busca en un diccionario; cuando se va a buscar una palabra que empieza por la letra "s", nadie comienza a leerse las palabras que empiezan por la "a", luego la "b", y así en adelante. Normalmente, se abre el diccionario por la mitad y, dependiendo de si la letra inicial por la que hemos abierto es mayor o menor que la que buscamos, descartamos la mitad de las palabras de la enciclopedia y ya solo buscamos en la mitad restante.
El pseudocódigo del algoritmo de búsqueda binaria se puede encontrar, por ejemplo, aquí. El algoritmo consiste en mantener unos índices que marcan los límites superior e inferior de la parte del vector que nos queda por analizar.
Para calcular la complejidad de este algoritmo, inicialmente en número de elementos por analizar es n. Tras la primera división, el número será como mucho n/2 (pues nos hemos quedado con la mitad de elementos); tras la segunda división, el número será como mucho n/4; y así sucesivamente. Por lo general, tras la división número i, el número de elementos por analizar será como mucho:
\[\frac{n}{2^i}\]
El peor caso se da cuando el elemento a buscar no se encuentra en el vector (es decir, cuando tras dividir los elementos por analizar nos quedemos con un número menor a 1). Por lo tanto, el número máximo de llamadas a realizar es el menor número m tal que:
\[\frac{n}{2^m} < 1\]
Transformando esta fórmula a un logaritmo en base 2, tenemos que:
\[n < 2^m\]
y que
\[\log n < m\]
es decir, que el número m depende, no del tamaño n del vector, sino del logaritmo de dicho n.
Es por esto que el algoritmo de búsqueda binaria tiene una complejidad de orden logarítmico (O(log n)).
Referencia:
Michael T. Goodrich y Roberto Tamassia. Data Structures and Algorithms in Java, Fifth edition. John Wiley & Sons. 2011.
Me ha servido bastante tu post para entender la complejidad logarítmica. Muchas gracias.
ResponderEliminarMe alegro. :)
ResponderEliminarmuy buena informacion
ResponderEliminarExplicació rápida y correcta. Muy útil.
ResponderEliminarSabes si existe un algoritmo o un programa que calcule la complejidad de otro algoritmo o seudo codigo?
ResponderEliminarNi idea. Creo que google te responderá a eso mejor que yo.
ResponderEliminartengo una duda, consideraste el peor caso haciendo divisiones hasta llegar a 0, pero si el numero buscado X es mayor al ultimo numero del arreglo, ejemplo tienes un arreglo de 100 numeros (0-99) y buscar el 5567 las divisiones y descartes para seguir buscando no cumplen tu condicion...("tras dividir los elementos por analizar nos quedemos con un número menor a 1")
ResponderEliminarHola, a lo mejor en el texto no queda muy claro. En el caso en el que el número a buscar sea mayor que todos los elementos va a pasar lo mismo, los límites van a ir disminuyendo y en el peor caso llegaremos hasta el último elemento del vector sin encontrar el valor.
ResponderEliminarExcelente! Gracias!
ResponderEliminarMuchas gracias!
ResponderEliminar