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

Question

[MishaXXL]

И так, есть у нас к примеру массив (массив может быть произвольной длинны).

const a = [1, 5, 20, 40, 3, 12, 6, 5, 77, 1, 11, 40]

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

Для наглядности возьмем пример
a.indexOf(77)
Предполагается, что для данного случая у нас может получится скорость O(3), если мы бы знали, что наши входные данные постоянно длинной в 12 элементов.
Но как быть, если у нас длинна массива всегда будет разная.

Comments

[WbICHA]

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

Откуда взялось число 3? И нет, это по прежнему O(n). Нам всё равно на лучший случай, нам нужен худший, а в худшем случае искомый элемент последний.

Answer 1

[Сергей П]

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

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

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

Comments

[mayton2019]

Не обязательно каждый раз рекомендовать Дональда Кнута. Не он один писал про complexity.
Есть Вирт, Седжвик, Кормен.

[MishaXXL]

Вряд ли же он реализован через данный алгоритм

Array.prototype.myIndexOf = function(val) {
	for(let i = 0; i < this.length; ++i) {
  	if(this[i] === val) return i
  }
  return -1
}

const a = [1, 5, 20, 40, 3, 12, 6, 5, 77, 1, 11, 40]

console.log(a.myIndexOf(77))

Как минимум мы для любого массива можем идти с начала и конца, сократив его в двое
Как тогда описать алгоритм, когда у нас не O(N), а образно O(N/2)
И в нашем случае, если у нас 12 элементов и мы бы создали 4 переменные, то за 3 итерации мы бы обошли весь массив и сравнили наличие наименьшего значение, если в первой переменной, которая от 0 до 3 не имела бы значения, искали ближайшее в следующих

[Сергей П]

MishaXXL, похоже нет никакого смысла вам что-то объяснять.
Нотация не показывает конкретное число итераций, а N и N/2 в этом контексте одно и то же.
Прочитайте учебник, иначе складывается впечатление, что вы и так сами лучше всех всё "знаете". Так какого ж черта сюда идти с детскими вопросами?
Если посчитать количество операций процессора, то в конечном итоге то на то и выйдет хоть с двух сторон иди по массиву, хоть с одной. Но с двух сторон - так никто не делает, потому что от поиска элемента ожидаешь. что находить он будет логично предсказуемый элемент, например первый попавшийся, или последний попавшийся. Да, некоторые алгоритмы не гарантируют какой элемент они вернут из нескольких, но так и задачу тогда надо яснее ставить.
К примеру, через хеш-функцию эта задача решается за амортизированную сложность порядка О(1), то есть среди не будет заметной разницы времени получения индекса числа из 10 или десяти миллионов значений.