@MishaXXL

Как реализовать идеальный метод indexOf?

И так, есть у нас к примеру массив (массив может быть произвольной длинны).
const a = [1, 5, 20, 40, 3, 12, 6, 5, 77, 1, 11, 40]

Как нам реализовать идеальный метод indexOf для массива с условием, что сложность O(N) нам не подходит, но при этом у нас нет фиксированного порога для максимально быстрого выполнения поиска?

Для наглядности возьмем пример
a.indexOf(77)
Предполагается, что для данного случая у нас может получится скорость O(3), если мы бы знали, что наши входные данные постоянно длинной в 12 элементов.
Но как быть, если у нас длинна массива всегда будет разная.
  • Вопрос задан
  • 119 просмотров
Решения вопроса 1
trapwalker
@trapwalker
Программист, энтузиаст
Вы неверно понимаете суть О-нотации. Почитайте книги Дональда Кнута про это.
O(3) - это то же самое, что O(1). Нет разницы. O(N), O(N+1000), O(10*N) - это тоже одно и то же.
В таких случаях речь всегда идёт не про конкретный кейс, а про обобщенный. Вы не знаете в каком порядке элементы вашего массива, где находится искомый, сколько всего элементов будет в конкретных кейсах, поэтому определяется ряд случаев: средний (по вероятности, если входные данные рандомные), худший (чтобы понимать границы и сколько может "висеть" алгоритм теоретически). Лучшие варианты обычно никого не интересуют, потому что и вероятность их мала, и смысла никакого нет в столь малых величинах.

У вас типичный случай компромисса в реализации структуры данных. Вы всегда балансируете между памятью и скоростью. Больших семь шапок из овцы не выкроить никак.
То есть, вы можете сделать такую структуру данных, которая "под капотом" будет держать древовидный индекс с данными или отсортированную по ключу карту значений для бинарного поиска. Хотя эти варианты - суть одно и то же.
Если не рассматривается вариант размена производительности на память, то в этой задаче у вас будет только O(N) без вариантов.
Если усложнить структуру данных, то можно добиться и O(logN) при поиске, и даже O(1). Почитайте как устроен словарь в питоне.

Да, помимо сложности поиска у вас будет сложность вставки в структуру новых элементов. И тут опять трейд-офф. Ну а что вы хотели?
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
SummerWeb Ярославль
от 120 000 до 180 000 ₽
КРАФТТЕК Санкт-Петербург
от 60 000 до 80 000 ₽
Brightdata Тель-Авив
от 5 500 до 6 500 $
19 июн. 2024, в 01:11
7000 руб./за проект
18 июн. 2024, в 23:10
15000 руб./за проект