Chiarimento della dichiarazione sui risultati della ricerca binaria di raccolta da javadoc

Question

Sono confuso sulla analisi delle prestazioni del binarySearch dal Collections

Dice:

Se l'elenco specificato non implementa l'interfaccia RandomAccess ed è grande, questo metodo farà una ricerca binaria basata su iteratore che esegue O (n) link traversali e O (log n) confronti di elementi.

Non so come interpretare questo O(n) + O(log n).

voglio dire non è peggio che semplicemente attraversando la-lista collegata e confrontare? Abbiamo ancora solo O(n).

Che cosa significa questa affermazione sulle prestazioni? Come detto, non riesco a capire la differenza da una semplice ricerca lineare nell'elenco collegato.

Che cosa sono la mia incomprensione qui?

Answer 1

Prima di tutto è necessario capire che senza l'interfaccia RandomAccess lo binarySearch non può semplicemente accedere, beh, all'elemento casuale dall'elenco, ma invece deve utilizzare un iteratore. Questo introduce il costo di O(n). Quando la collezione implementa RandomAccess, il costo di ciascun accesso agli elementi è O(1) e può essere ignorato per quanto riguarda la complessità asintotica.

Perché O(n) è maggiore di O(log n) avrà sempre la precedenza su O(log n) e domina la complessità. In questo caso, binarySearch ha la stessa complessità della semplice ricerca lineare. Quindi qual è il vantaggio?

Ricerca lineare esegue confronti O(n), al contrario di O(log n) con binarySearch senza accesso casuale. Questo è particolarmente importante quando la costante prima di O(logn) è alta. In italiano semplice: quando il confronto singolo ha un costo molto elevato rispetto all'avanzante iteratore. Questo potrebbe essere uno scenario abbastanza comune, quindi limitare il numero di confronti è vantaggioso. Profitto!

Answer 2

La ricerca binaria non è adatta per gli elenchi collegati. L'algoritmo dovrebbe beneficiare di una raccolta ordinata con accesso casuale (come una matrice semplice), in cui può passare rapidamente da un elemento a un altro, suddividendo lo spazio di ricerca rimanente in due su ciascuna iterazione (da cui la complessità temporale O(log N)) .

Per un elenco collegato, c'è una versione modificata che scorre tutti gli elementi (e deve passare attraverso gli elementi 2n nel caso peggiore), ma invece di confrontare ogni elemento, "sonda" l'elenco solo nelle posizioni specificate (quindi facendo un numero inferiore di confronti rispetto a una ricerca lineare).

Poiché i confronti sono in genere leggermente più costosi rispetto alla semplice iterazione del puntatore, il tempo totale dovrebbe essere inferiore. Questo è il motivo per cui la parte log N viene enfatizzata separatamente.