¿Podemos buscar en una lista enlazada ordenada mejor que en tiempo O(n)? El tiempo de búsqueda en el peor de los casos para una lista enlazada ordenada es O (n), ya que solo podemos recorrer la lista de forma lineal y no podemos omitir Nodes durante la búsqueda. Para un árbol de búsqueda binario equilibrado, omitimos casi la mitad de los Nodes después de una comparación con la raíz. Para una array ordenada, tenemos acceso aleatorio y podemos aplicar la búsqueda binaria en las arrays. ¿Podemos aumentar las listas enlazadas ordenadas para buscar más rápido? La respuesta es Saltar lista. La idea es simple, creamos múltiples capas para que podamos omitir algunos Nodes. Consulte la siguiente lista de ejemplo con 16 Nodes y dos capas. La capa superior funciona como un «carril rápido» que conecta solo las principales estaciones exteriores, y la capa inferior funciona como un «carril normal» que conecta todas las estaciones. Supongamos que queremos buscar 50, comenzamos desde el primer Node del «carril rápido» y seguimos moviéndonos en el «carril rápido» hasta que encontramos un Node cuyo siguiente es mayor que 50. Una vez que encontramos dicho Node (30 es el Node en el siguiente ejemplo) en «carril rápido», nos movemos a «carril normal» usando un puntero de este Node, y buscamos linealmente 50 en «carril normal». En el siguiente ejemplo, partimos de 30 en el «carril normal» y con búsqueda lineal, encontramos 50. ¿Cuál es la complejidad de tiempo con dos capas?
En el peor de los casos, la complejidad del tiempo es varios Nodes en el «carril rápido» más varios Nodes en un segmento (un segmento son varios Nodes de «carril normal» entre dos Nodes de «carril rápido») del «carril normal». Entonces, si tenemos n Nodes en el «carril normal», √n (raíz cuadrada de n) Nodes en el «carril rápido» y dividimos equitativamente el «carril normal», entonces habrá √n Nodes en cada segmento del «carril normal». ”. √n es una división óptima con dos capas. Con este arreglo, el número de Nodes atravesados para una búsqueda será O(√n). Por lo tanto, con O(√n) espacio extra, podemos reducir la complejidad del tiempo a O(√n).
Ventajas de la lista de saltos:
- La lista de saltos es sólida y confiable.
- Para agregarle un nuevo Node, se insertará extremadamente rápido.
- Fácil de implementar en comparación con la tabla hash y el árbol de búsqueda binaria
- El número de Nodes en la lista de omisión aumenta y la posibilidad del peor de los casos disminuye
- Requiere solo tiempo Θ(logn) en el caso promedio para todas las operaciones.
- Encontrar un Node en la lista es relativamente sencillo.
Desventajas de la lista de saltos:
- Necesita una mayor cantidad de memoria que el árbol balanceado.
- No se permite la búsqueda inversa.
- La búsqueda es más lenta que una lista enlazada
- Las listas de exclusión no son aptas para caché porque no optimizan la localidad de referencia
¿Podemos hacerlo mejor? La complejidad temporal de las listas de omisión se puede reducir aún más agregando más capas. La complejidad de tiempo de la búsqueda, la inserción y la eliminación puede convertirse en O (Iniciar sesión) en casos promedio con O (n) espacio adicional. Pronto publicaremos más publicaciones en Skip Lists. Referencias Conferencia en video del MIT sobre listas de exclusión http://en.wikipedia.org/wiki/Skip_list Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA