algorithm - recursiva - cómo aplicar la búsqueda binaria O(log n) en una lista enlazada ordenada?
busqueda secuencial en c++ (6)
Recientemente me encontré con una pregunta interesante en la lista vinculada. Se proporciona una lista enlazada individualmente ordenada y tenemos que buscar un elemento de esta lista.
La complejidad del tiempo no debe ser mayor que O(log n) . Parece que tenemos que aplicar la búsqueda binaria en esta lista vinculada. ¿Cómo? Como la lista vinculada no proporciona acceso aleatorio si tratamos de aplicar el algoritmo de búsqueda binaria, alcanzará O (n) ya que necesitamos encontrar la longitud de la lista e ir al centro.
¿Algunas ideas?
Ciertamente no es posible con una simple lista enlazada por separado.
Prueba de boceto: para examinar el último nodo de una lista de enlace único, debemos realizar n-1 operaciones de seguir un puntero "siguiente" [prueba por inducción sobre el hecho de que solo hay una referencia al k+1 nodo, y está en el késimo nodo, y se necesita una operación para seguirlo]. Para ciertas entradas, es necesario examinar el último nodo (específicamente, si el elemento buscado es igual o mayor que su valor). Por lo tanto, para ciertas entradas, el tiempo requerido es proporcional a n .
O necesita más tiempo o una estructura de datos diferente.
Tenga en cuenta que puede hacerlo en comparaciones O (log n) con una búsqueda binaria. Simplemente tomará más tiempo que eso, por lo que este hecho solo es de interés si las comparaciones son mucho más caras que el recorrido de la lista.
Como se señaló, esto no es en general posible. Sin embargo, en un lenguaje como C, si los nodos de lista están asignados contiguamente, sería posible tratar la estructura como una matriz de nodos.
Obviamente, esto es solo una respuesta a una variante de pregunta trucada de este problema, pero el problema siempre es una imposibilidad o una pregunta capciosa.
En la Lista enlazada, la búsqueda binaria puede no alcanzar una complejidad de O (log n) pero se puede lograr un poco usando el Método de doble puntero como se describe aquí en este trabajo de investigación: http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf
Necesita usar la lista de omisiones . Esto no es posible con una lista enlazada normal (y realmente quiero saber si esto es posible con la lista normal).
Sí, es posible en lenguaje Java como a continuación ..
Collections.<T>binarySearch(List<T> list, T key)
para la búsqueda binaria en cualquier List . Funciona en ArrayList y en LinkedList y en cualquier otra List .
Usa MAPS para crear LINK LISTS.
Mapa M, M [primer elemento] = segundo elemento, M [segundo elemento] = tercer elemento,
...
...
es una lista enlazada ...
pero porque es un mapa ...
que internamente utiliza la búsqueda binaria para buscar cualquier elemento.
cualquier búsqueda de elementos tomará O (log n)