Самый быстрый алгоритм поиска максимума в массиве

5
16769
Добавить в избранное

Какой алгоритм для поиска максимума в случайном массиве использовать? В статье собрано 5 эффективных must-have алгоритмов.

Самый быстрый алгоритм поиска максимума в массиве

Самый быстрый и простейший алгоритм

Следует пояснить, что под «быстротой» алгоритма будет подразумеваться его асимптотическая сложность, а не физическое время выполнения.

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

Простейшая реализация алгоритма на С:

А как насчет распараллеливания?

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

Рассмотрим ситуацию на примере. Есть 200 карточек, на каждой из которых случайное число. Ваша задача найти карточку с самым большим числом. Допустим, друг согласился помочь, забрав половину карточек. Теперь каждый из вас ищет максимум из 100 карточек, вместо 200. Как только вы оба закончите, останется сравнить максимумы обеих половин. Время сократилось вдвое, но просмотреть пришлось все 200 карточек.

Сама по себе задача является так называемой чрезвычайно параллельной задачей, что ещё раз подтверждает возможность её решения именно распараллеливанием, без ущерба для конечного результата.

Задача о разборчивой невесте

Есть ещё один вариант нахождения максимума в случайном массиве.
Идем по первой половине всех значений в массиве. Запоминаем самое большое. Назовём его Х. Далее проходим по второй половине. Когда (и если) находим значение, которое больше Х, останавливаемся. Обозначим его Y. Какова вероятность того, что Y – максимум в массиве?

Чтобы это утверждение было истинным, Y должно находиться во второй половине массива. А так как значения в массиве случайны, шанс такого = 50%. Тогда если второй максимум присутствует в первой половине, это гарантирует, что найден правильный максимум.

Вероятность, что второй максимум в первой половине также = 50%. Посему вероятность, что и второй максимум в первой половине, и первый максимум во второй половине, равна 25%.

В итоге, такой алгоритм гарантирует точность 25% в нахождении максимума в массиве случайных чисел. Можно улучшить алгоритм, если искать второй максимум не в первой половине (1/2), а в 1/e (основание натурального логарифма) части массива. Этот способ впервые был предложен для решения задачи о разборчивой невесте или задачи секретаря (The Secretary Problem).

Аналоговый алгоритм

Спагетти-сортировка — прекрасный аналоговый алгоритм для решения задачи нахождения максимума в массиве.

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

Асимптотическая сложность такого алгоритма – O(1). Но в цифровом мире он не применим.

Квантовый алгоритм

Алгоритм Гровера (или схема Гровера) используется в квантовых вычислениях для решения задач перебора. С его помощью сложность поиска максимума уменьшается до O(sqrt(N)) (большая О от корня N).

Данный способ решения может быть применен только на квантовом компьютере, что сильно умаляет его полезность в современном мире, но его нельзя не упомянуть.

Источник

Хотите дополнить? Ждём ваши предложения в комментариях 😉

Интересуетесь алгоритмами?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




Комментариев: 5

  1. Борис Худорожков

    Принцип спагетти можно применить если предварительно известны размеры выборки. Т.е поднимая планку выбора сравнивать между собой количество=K данных. В лучшем случае количество переборов будет =1 в худшем N+K(0)+……….K(i).В среднем если хорошо известен размер спагете можно получить меньше N

  2. Иван Петров

    уровень решений — школа. местами, даже для школы оценка не более 3.

  3. Игорь Божко

    Почему не сложить сумму всех значений, а потом разделив на количество значений, сравнивать только оставшиеся? Либо провести с ними такойже алгоритм?

    1. Потому, что это ещё хуже, чем просто перебрать элементы и найти максимум

    2. Федор Инкогнито

      Сложность предложенного вами алгоритма 2N+N+N/2+N/4… . По крайней мере именно столько итераций сложения и сравнения вас предется совершить с элементами массива. Что несколько больше чем сложность самого первого алгоритма(N) 🙂

Добавить комментарий