Самый быстрый алгоритм для поиска самого большого значения в неотсортированном массиве?

Question

[cybran24]

Возможно, линейный поиск? Но он не используется в продкашене, на сколько мне известно. Тогда, Поиск с сортировкой? Но ведь на сортировку тоже тратится время и выходит, что он уступает в скорости линейному?

Comments

[Модератор]

cybran24 дорогой пользователь, настоятельно рекомендуем еще раз обратить самое пристальное внимание на п. 3.1 регламента работы сервиса (и, в особенности, на его последний абзац).
В противном случае, ваши вопросы будут удаляться по причине тег-спама, а систематические нарушения приведут к блокировке учетной записи.

Answer 1

[dollar]

в неотсортированном массиве

O(n)
То есть полный перебор.

Но он не используется в продкашене

Вам нужен самый быстрый алгоритм или соответствие (мнимому) продакшену?

Comments

[GavriKos]

Плюсую. Если структура данных жестко задана - то без вариантов.

[cybran24]

GavriKos, спасибо!

Answer 2

[xmoonlight]

(Если уж так случилось!)
В 2 последовательных прохода.
1. По объему данных в каждом элементе массива (объём памяти, занимаемой данными).
2. По самим данным, в элементах массива с наибольшим объёмом занимаемой памяти.

Это будет значительно быстрее, чем сразу сравнивать данные прямым перебором.

Вообще, такие случаи, как появление или наличие неотсортированного массива, говорят о том, что архитектор программного решения/комплекса вообще не умеет работать с данными.