Разъяснение заявления о выполнении бинарного поиска в коллекции от javadoc

Question

Я запутался в анализе производительности binarySearch из коллекций

В нем говорится:

Если указанный список не реализует RandomAccessинтерфейс и большой, этот метод будет делать бинарный поиск на основе итератора, который выполняет O (n) обход ссылок и O (log n) сравнения элементов.

Я не уверен, как это интерпретировать O(n) + O(log n).

Я имею в виду, разве это не хуже, чем просто просмотреть связанный список и сравнить?Мы все еще получаем только O(n).

Так что же означает это утверждение о производительности?Как сформулировано, я не могу понять разницу от простого линейного поиска в связанном списке.

Что я здесь недопонимаю?

Answer 1

Прежде всего, вы должны понимать, что без RandomAccess интерфейса binarySearch не может просто получить доступ к случайному элементу из списка, но вместо этого он должен использовать итератор. Это вводит O(n) стоимость. Когда в коллекции реализовано RandomAccess, стоимость доступа к каждому элементу равна O(1) и может быть проигнорирована в отношении асимптотической сложности.

Поскольку O(n) больше O(log n), оно всегда будет иметь приоритет над O(log n) и будет доминировать в сложности. В этом случае binarySearch имеет ту же сложность, что и простой линейный поиск. Так в чем же преимущество?

Линейный поиск выполняет сравнение O(n), в отличие от O(log n) с binarySearch без произвольного доступа. Это особенно важно, когда константа перед O(logn) высока. Говоря простым языком: , когда одиночное сравнение стоит очень дорого по сравнению с продвигающимся итератором . Это может быть довольно распространенным сценарием, поэтому ограничение числа сравнений выгодно. Прибыль!

Answer 2

Бинарный поиск не подходит для связанных списков.Предполагается, что алгоритм извлекает выгоду из отсортированной коллекции со случайным доступом (как простой массив), где он может быстро переходить от одного элемента к другому, разделяя оставшееся пространство поиска на две на каждой итерации (отсюдаO(log N) сложность по времени).

Для связанного списка существует модифицированная версия, которая перебирает все элементы (и в худшем случае должна проходить элементы 2n), но вместо сравнения каждого элемента, он "исследует" список только в указанных позициях (следовательно, делает меньшее число сравнений по сравнению с линейным поиском).

Поскольку сравнения обычно немного дороже по сравнению с итерацией простого указателяОбщее время должно быть ниже.Вот почему часть log N выделена отдельно.