Несколько алгоритмов для поиска максимального значения в массиве чисел:

• Перебор. 12 Для сохранения найденного значения используется переменная, которой изначально присваивается первый элемент списка. 1 В цикле каждый элемент сравнивается с этой переменной. 1 Если он больше, то значение этого элемента сохраняется в переменной. 1 После сравнения со всеми членами списка в переменной гарантированно находится наибольший элемент. 1
• Задача о разборчивой невесте. 2 Нужно пройти по первой половине всех значений в массиве и запомнить самое большое. 2 Далее пройти по второй половине и, когда будет найдено значение, которое больше запомненного, остановиться. 2 Такой алгоритм гарантирует точность 25% в нахождении максимума в массиве случайных чисел. 2
• Аналоговый алгоритм «Спагетти-сортировка». 2 Нужно взять N не приготовленных палочек спагетти, длина каждой сопоставляется с единственным значением в массиве. 2 Затем собрать спагетти в руку и аккуратно поставить горсть на ровную поверхность. 2 В результате выше всех будет видна самая длинная (максимум) соломинка. 2 Асимптотическая сложность такого алгоритма — O(1). 2
• Квантовый алгоритм. 2 Алгоритм Гровера (или схема Гровера) используется в квантовых вычислениях для решения задач перебора. 2 С его помощью сложность поиска максимума уменьшается до O(sqrt(N)). 2 Данный способ решения может быть применён только на квантовом компьютере. 2