Aclaración de estado de rendimiento de búsqueda binaria de recogida de javadoc

Question

estoy confundido en el análisis del rendimiento de binarySearch del Collections

Dice:

Si la lista especificada no implementa la interfaz de acceso aleatorio y es grande, este método realizará una búsqueda binaria basada en iteradores que realiza O (n) cruces de enlaces y comparaciones de elementos O (log n).

No estoy seguro de cómo interpretar esto O(n) + O(log n).

Quiero decir, ¿no es peor que simplemente atravesar la lista enlazada y comparar? Todavía obtenemos solo O(n).

Entonces, ¿qué significa esta afirmación sobre el rendimiento? Tal como está redactado, no puedo entender la diferencia de una búsqueda lineal simple en la lista vinculada.

¿Qué es lo que no entiendo aquí?

Answer 1

En primer lugar, debe comprender que, sin la interfaz RandomAccess, el binarySearch no puede simplemente acceder, bueno, al azar a un elemento de la lista, sino que debe usar un iterador. Eso introduce el costo O(n). Cuando la colección implementa RandomAccess, el costo del acceso de cada elemento es O(1) y se puede ignorar en lo que se refiere a la complejidad asintótica.

Porque O(n) es mayor que O(log n) siempre tendrá prioridad sobre O(log n) y dominará la complejidad. En este caso, binarySearch tiene la misma complejidad que la búsqueda lineal simple. Entonces, ¿cuál es la ventaja?

La búsqueda lineal realiza O(n) comparaciones, a diferencia de O(log n) con binarySearch sin acceso aleatorio. Esto es especialmente importante cuando la constante anterior a O(logn) es alta. En inglés simple: cuando la comparación individual tiene un costo muy alto en comparación con el iterador avanzado. Este podría ser un escenario bastante común, por lo que limitar el número de comparaciones es beneficioso. ¡Lucro!

Answer 2

La búsqueda binaria no es adecuada para listas vinculadas. Se supone que el algoritmo se beneficia de una colección ordenada con acceso aleatorio (como una matriz simple), donde puede saltar rápidamente de un elemento a otro, dividiendo el espacio de búsqueda restante en dos en cada iteración (de ahí la complejidad de tiempo O(log N)) .

Para una lista vinculada, hay una versión modificada que recorre todos los elementos (y necesita pasar por 2n elementos en el peor de los casos), pero en lugar de comparar cada elemento, "sondea" la lista solo en posiciones especificadas (haciendo un menor número de comparaciones en comparación con una búsqueda lineal).

Dado que las comparaciones suelen ser un poco más costosas en comparación con la iteración de puntero normal, el tiempo total debería ser menor. Es por eso que la pieza log N se enfatiza por separado.