Уточнение утверждения выполнения бинарного поиска коллекции из javadoc

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

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

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

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

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

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

Что я пропущу здесь?

Ответ 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) высока. На простом английском языке: когда одно сравнение имеет очень высокую стоимость по сравнению с продвижением итератора. Это может быть довольно распространенным сценарием, поэтому ограничение количества сравнений выгодно. Прибыль!

Ответ 2

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

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

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