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

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

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

• углубишься в решение практических задач;
• узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.

Ты также будешь на связи с преподавателем и другими студентами.

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

Интересно, хочу попробовать

---

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

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

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

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

#include <stdio.h>
 
int main()
{
  int array[100];
  int maximum, size, index = 0;
 
  printf("Введите длину массива (не больше 100)\n");
  scanf("%d", &size);
 
  printf("Введите %d целых чисел массива\n", size);
  for (int i = 0; i < size; i++)
    scanf("%d", &array[i]);
 
  maximum = array[0]; // За изначальный максимум берем первый элемент массива
 
  for (int i = 1; i < size; i++)
  {
    if (array[i] > maximum)
    {
       maximum  = array[i];
       index = i;
    }
  }
 
  printf("Максимум находится в позиции %d и его значение %d.\n", index, maximum);
  return 0;
}

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

После прочтения абзаца выше многие могут предложить поиск максимума с помощью параллельных вычислений, потому что он будет быстрее. И это так, если мы говорим о физическом времени. Но несмотря на то, сколько у вас есть процессов, вам всё равно придется просмотреть каждый элемент массива. Сложность алгоритма остается такой же, 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).

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

Источник

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