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


Оглавление (нажмите, чтобы открыть):

Алгоритм нахождения минимума и максимума в данном наборе

Большой массив array[n] целых чисел дается в качестве входных данных. Даны два значения индекса: start,end , Желательно найти очень быстро — min & max in the set [start,end] (включительно) и max in the rest of array (исключая [начало, конец]).

массив — 3 4 2 2 1 3 12 5 7 9 7 10 1 5 2 3 1 1

начало, конец — 2,7

мин, максимум в [2,7] — 1,12

максимум в покое — 10

Я не могу придумать ничего лучше линейного. Но это не достаточно хорошо, как n is of order 10^5 и число таких операций поиска также имеет тот же порядок.

Любая помощь будет высоко оценен.

Решение

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

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

Другие решения

Насколько я понимаю, ваш вопрос заключается в том, что вы хотите выполнить некоторую предварительную обработку фиксированного массива, которая затем сделает вашу операцию find max очень быстрой.

В этих ответах описан подход, который выполняет предварительную обработку O (nlogn), за которой следует O (1) для каждого запроса.

Предварительная обработка O (nlogn)

Идея состоит в том, чтобы подготовить два 2d массива BIG [a, k] и SMALL [a, k], где

Вы можете вычислить эти массивы рекурсивным способом, начиная с k == 0, а затем создавая значение для каждого более высокого элемента, комбинируя два предыдущих элемента вместе.

Lookup O (1) за запрос

После этого вы сможете мгновенно найти максимальное и минимальное значения для любого диапазона, комбинируя 2 подготовленных ответа.

Предположим, вы хотите найти максимум для элементов от 100 до 133.
Вы уже знаете максимум 32 элемента от 100 до 131 (в BIG [100,5]), а также максимум 32 элемента от 102 до 133 (в BIG [102,5]), поэтому вы можете найти самый большой из них, чтобы получить ответ.

Та же логика применима к минимуму. Вы всегда можете найти два перекрывающихся подготовленных ответа, которые будут объединены, чтобы дать нужный вам ответ.

Я боюсь, что нет более быстрого пути. Ваши данные абсолютно случайны, и таким образом, вы должны пройти через все значения.
Даже сортировка не поможет, потому что в лучшем случае O (n log n), поэтому она медленнее. Вы не можете использовать метод деления пополам, потому что данные не отсортированы. Если вы начнете строить структуры данных (например, кучи), это снова будет O (n log n) в лучшем случае.

Если массив очень большой, разбейте его на разделы и используйте потоки для линейной проверки каждого раздела. Затем выполните min / max с результатами из потоков.

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

Но я не верю, что это на самом деле быстрее. Подумайте о том, чтобы написать это в сборке.

РЕДАКТИРОВАТЬ:
При сравнении строк этот алгоритм мог сделать разницу!

Если вы знаете мин, вы можете проверить от х до мин, если значение существует в массиве. Если вы знаете максимум, вы можете проверить (в обратном направлении) от y до max, если значение существует в массиве, вы нашли max.

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

Вы устанавливаете x равным 0, проверяете, существует ли 0, нет, затем вы изменяете его на 1, вы обнаруживаете 1. есть ваш мин.
Вы установили y равным 15 (произвольно большое число): существует? нет. установлено на 14. существует? нет, установлено на 13. существует? нет. установлено на 12. существует? да! там твой максимум! Я только что сделал 4 сравнения.

Если y существует с первой попытки, возможно, вы проверили значение ВНУТРИ массива. Итак, вы тестируете его снова с помощью y + length / 2. Предположим, вы нашли центр массива, поэтому немного добавьте декаль. Если вы снова нашли значение с первой попытки, оно может быть в массиве.

Если у вас отрицательные значения и / или значения с плавающей запятой, эта методика не работает ��

Конечно, не возможно иметь сублинейный алгоритм (насколько я знаю), чтобы искать, как вы хотите. Тем не менее, вы можете достичь сублинейного времени в некоторых случаях, сохраняя фиксированные диапазоны min-max, и, зная диапазон, вы можете улучшить время поиска.
например если вы знаете, что «большая часть» временного диапазона поиска будет, скажем, 10, то вы можете хранить минимум-максимум 10/2 = 5 элементов отдельно и индексировать эти диапазоны. Во время поиска вы должны найти расширенный набор диапазонов, которые могут относиться к диапазону поиска.

например в примере
массив — 3 4 2 2 1 3 12 5 7 9 7 10 1 5 2 3 1 1

начало, конец — 2,7

мин, максимум в [2,7] — 1,12

если вы «знаете», что большая часть диапазона времени поиска будет состоять из 5 элементов, вы можете предварительно индексировать min-max, например: с 5/2 = 2,

Я думаю, этот метод будет работать лучше, когда диапазоны велики, так что сохранение min-max позволяет избежать некоторых поисков.

Для поиска min-max [2-7] вы должны искать сохраненные индексы, такие как: 2/2 = от 1 до 7/2 = 3,
тогда минимум минут (2,1,5) даст вам минимум (1), а максимум максимумов (2,3,12) даст вам максимум (12). В случае перекрытия вам придется искать только угловые индексы (линейно). Тем не менее, это может избежать нескольких поисков, я думаю.

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

Линейный это лучшее, что вы можете сделать, и его относительно легко доказать.

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

Кроме того, мы уберем вашу задачу поиска мин / макс в подстроке. Мы будем думать о них обоих как о по сути одной и той же механической проблеме. Один волшебным образом отслеживает числа, меньшие, чем другие числа в сравнении, и один волшебным образом отслеживает числа, большие, чем в сравнении. Это действие считается бесплатным.

Затем давайте отбросим мин / макс задачи подмассива, потому что это та же проблема, что и мин / макс любого массива, и мы будем волшебным образом предполагать, что она решена и как часть нашего общего действия по нахождению Макс в большем массиве. Мы можем сделать это, предполагая, что наибольшее число во всем массиве на самом деле является первым числом, на которое мы обращаем внимание некоторой магической случайностью, и это также самое большое число в подмассиве, а также наименьшее число в суб-массив, но мы просто не знаем, как нам повезло. Как мы можем узнать?

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

Сколько сравнений нам нужно сделать? Мы позволим N быть длиной массива, а общее число операций для любой длины N равно N — 1. Поскольку мы добавляем элементы в массив, число сравнений масштабируется с одинаковой скоростью, даже если все наши широко Возмутительные предположения подтвердились.

Итак, мы подошли к точке, где N — это и длина массива, и определяющий фактор увеличения стоимости наилучшей возможной операции в нашем дико нереалистичном лучшем случае.

Ваша операция масштабируется с N в лучшем случае. Мне жаль.

/ сортировка входных данных должна быть более дорогой, чем эта минимальная операция, поэтому она будет применима только в том случае, если вы выполняли операцию несколько раз и не имели возможности сохранить фактические результаты, что маловероятно, поскольку 10 ^ 5 ответов это не совсем налоги.

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

/// Я предполагаю, что на самом деле это должно быть особенно любопытным явлением для чего-либо, что когда-либо масштабируется лучше, чем линейно, не предполагая что-то о данных … stackoverflowers?

Поиск подотрезка массива с максимальной/минимальной суммой

Здесь мы рассмотрим задачу о поиске подотрезка массива с максимальной суммой («maximum subarray problem» на английском), а также некоторые её вариации (в том числе алгоритм решения варианта этой задачи в режиме онлайн — описанный автором алгоритма — KADR (Ярослав Твердохлеб)).

Постановка задачи

Дан массив чисел . Требуется найти такой его подотрезок , что сумма на нём максимальна:

Например, если бы все числа массива были бы неотрицательными, то в качестве ответа можно было бы взять весь массив. Решение нетривиально, когда массив может содержать как положительные, так и отрицательные числа.

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

Алгоритм 1

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

Описание алгоритма

Алгоритм весьма прост.

Введём для удобства обозначение: . Т.е. массив — это массив частичных сумм массива . Также положим значение .

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

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

Отсюда мы сразу получаем алгоритм решения: мы просто будем хранить, где в массиве находится текущий минимум. Используя этот минимум, мы за находим текущий оптимальный индекс , а при переходе от текущего индекса к следующему мы просто обновляем этот минимум.

Мастер Йода рекомендует:  Подключение к базе данных с помощью JDBC

Очевидно, этот алгоритм работает за и асимптотически оптимален.

Реализация

Для реализации нам даже не понадобится явно хранить массив частичных сумм — от него нам будет требоваться только текущий элемент.


Реализация приводится в 0-индексированных массивах, а не в 1-нумерации, как было описано выше.

Приведём сначала решение, которое находит просто численный ответ, не находя индексы искомого отрезка:

Теперь приведём полный вариант решения, который параллельно с числовым решением находит границы искомого отрезка:

Алгоритм 2

Здесь мы рассмотрим другой алгоритм. Его чуть сложнее понять, но зато он более элегантен, чем приведённый выше, и реализуется чуть-чуть короче. Этот алгоритм был предложен Джеем Каданом (Jay Kadane) в 1984 г.

Описание алгоритма

Сам алгоритм выглядит следующим образом. Будем идти по массиву и накапливать в некоторой переменной текущую частичную сумму. Если в какой-то момент окажется отрицательной, то мы просто присвоим . Утверждается, что максимум из всех значений переменной , случившихся за время работы, и будет ответом на задачу.

Докажем этот алгоритм.

В самом деле, рассмотрим первый момент времени, когда сумма стала отрицательной. Это означает, что, стартовав с нулевой частичной суммы, мы в итоге пришли к отрицательной частичной сумме — значит, и весь этот префикс массива, равно как и любой его суффикс имеют отрицательную сумму. Следовательно, от всего этого префикса массива в дальнейшем не может быть никакой пользы: он может дать только отрицательную прибавку к ответу.

Однако этого недостаточно для доказательства алгоритма. В алгоритме мы, фактически, ограничиваемся в поиске ответа только такими отрезками, которые начинаются непосредственно после мест, когда случалось .

Но, в самом деле, рассмотрим произвольный отрезок , причём не находится в такой «критической» позиции (т.е. p+1″>, где — последняя такая позиция, в которой ). Поскольку последняя критическая позиция находится строго раньше, чем в , то получается, что сумма неотрицательна. Это означает, что, сдвинув в позицию , мы увеличим ответ или, в крайнем случае, не изменим его.

Так или иначе, но получается, что действительно при поиске ответа можно ограничиться только отрезками, начинающимися сразу после позиций, в которых оказывалось . Это доказывает правильность алгоритма.

Реализация

Как и в алгоритме 1, приведём сначала упрощённую реализацию, которая ищет только числовой ответ, не находя границ искомого отрезка:

Полный вариант решения, с поддержанием индексов-границ искомого отрезка:

Смежные задачи

Поиск максимального/минимального подотрезка с ограничениями

Если в условии задачи на искомый отрезок накладываются дополнительные ограничения (например, что длина отрезка должна находиться в заданных пределах), то описанный алгоритм скорее всего легко обобщается на эти случаи — так или иначе, задача будет по-прежнему заключаться в поиске минимума в массиве при заданных дополнительных ограничениях.

Двумерный случай задачи: поиск максимальной/минимальной подматрицы

Описанная в данной статье задача естественно обобщается на большие размерности. Например, в двумерном случае она превращается в поиск такой подматрицы заданной матрицы, которая имеет максимальную сумму чисел в ней.

Из описанного выше решения для одномерного случая легко получить решение за : переберём и , и посчитаем массив сумм с по в каждой строке матрицы; мы пришли к одномерной задаче поиска индексов и в этом массиве, которую уже можно решать за линейное время.

Более быстрые алгоритмы решения этой задачи хотя и известны, однако они не сильно быстрее , и при этом весьма сложны (настолько сложны, что по скрытой константе многие из них уступают тривиальному алгоритму при всех разумных ограничениях). По всей видимости, лучший из известных алгоритмов работает за (T. Chan 2007 «More algorithms for all-pairs shortest paths in weighted graphs»).

Этот алгоритм Chan, а также многие другие результаты в данной области на самом деле описывают быстрое умножение матриц (где под умножением матриц подразумевается модифицированное умножение: вместо сложения используется минимум, а вместо умножения — сложение). Дело в том, что задача о поиске подматрицы с наибольшей суммой сводится к задаче о поиске кратчайших путей между всеми парами вершин, а эта задача, в свою очередь — сводится к такому умножению матриц.

Поиск подотрезка с максимальной/минимальной средней суммой

Эта задача заключается в том, что надо найти такой отрезок , чтобы среднее значение на нём было максимальным:

Конечно, если на искомый отрезок по условию не наложено других условий, то решением всегда будет являться отрезок длины в точке-максимуме массива. Задача имеет смысл, только если имеются дополнительные ограничения (например, длина искомого отрезка ограничена снизу).

В таком случае применим стандартный приём при работе с задачами о среднем значении: будем подбирать искомую максимальную среднюю величину двоичным поиском.

Для этого нам надо научиться решать такую подзадачу: дано число , и надо проверить, есть ли подотрезок массива (конечно, удовлетворяющий всем дополнительным ограничениям задачи), на котором среднее значение больше .

Чтобы решить эту подзадачу, отнимем от каждого элемента массива . Тогда наша подзадача фактически превращается в такую: есть или нет в данном массиве подотрезок положительной суммы. А эту задачу мы уже умеем решать.

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

Решение задачи в режиме онлайн

Условие задачи таково: дан массив из чисел, а также дано число . Поступают запросы вида , и в ответ на запрос требуется найти подотрезок отрезка длины не менее с максимально возможным средним арифметическим.

Алгоритм решения этой задачи достаточно сложен. Автор данного алгоритма — KADR (Ярослав Твердохлеб) — описал данный алгоритм в своём сообщении на форуме.

Уроки 55 — 57
Поиск наибольшего и наименьшего элементов массива
(§ 20. Поиск наибольшего и наименьшего элементов массива)
Составление программы на Паскале
поиска минимального и максимального элементов

Содержание урока

§ 20. Поиск наибольшего и наименьшего элементов массива. Поиск максимума и минимума в электронной таблице

§ 20. Поиск наибольшего и наименьшего элементов массива
Поиск максимума и минимума в электронной таблице

Поиск максимума и минимума в электронной таблице

Одной из типовых задач обработки массивов является поиск наибольшего или наименьшего значения среди значений его элементов. Построим алгоритм решения этой задачи и составим программу на Паскале. Для примера возьмем итоговые данные чемпионата России по футболу в премьер-лиге за 2003 год.

На рисунке 2.12 показана электронная таблица с итогами чемпионата. В столбце А расположены названия команд, в столбце В — количество очков, набранных каждой командой. Команды перечислены в алфавитном порядке. Победителем является команда, набравшая наибольшее количество очков. Команда, набравшая очков меньше всех других, в следующем сезоне покидает премьер-лигу.

Для определения максимального значения в электронной таблице существует функция МАКС(), а для нахождения минимального значения — функция МИН( ). В ячейке B17 записана формула МАКС(В1:В16), а в ячейке В18 — формула МИН(В1:В16). Результаты вы видите в таблице. Отсюда делаем вывод: чемпионом России стала команда ЦСКА, а на последнем месте — «Черноморец».

Блок-схемы алгоритмов поиска максимума и минимума в массиве

Разберемся, как же программируется определение максимального и минимального значений в числовом массиве. Начнем с поиска максимума. Опишем алгоритм на Алгоритмическом языке.

Пусть в целочисленный массив B[1:16] заносятся очки команд в том порядке, в каком они расположены в таблице на рис. 2.12. Максимальное количество очков получим в переменной МахВ. Кроме того, найдем еще и номер команды, занявшей первое место. Для этого будем использовать переменную Nmax.

Рассмотрим алгоритм решения задачи. Алгоритм будет составлен исходя из упрощающего предположения о том, что максимальное количество баллов набрала только одна команда. Именно ее номер и будет выведен в качестве результата. Более общий вариант предлагается для рассмотрения в задании к данному параграфу. Ниже приведен полный алгоритм на Алгоритмическом языке, а на рис. 2.13 — фрагмент блок-схемы, относящийся только к выбору максимального элемента (без ввода и вывода).

Идея алгоритма состоит в следующем. В переменную МахВ заносится значение первого элемента массива, в переменную Nmax — единица, т. е. номер первого элемента. Затем в цикле последовательно с МахВ сравниваются все остальные элементы массива В. Если очередной элемент оказывается больше текущего значения МахВ, то его значение заносится в МахВ, а его номер — в Nmax. Когда закончится цикл, в МахВ останется наибольшее число из всего массива, а в Nmax — его номер.

Теперь нетрудно догадаться, как искать минимальное значение в массиве и его номер. Если для этого использовать в программе переменные MinB и Nmin и в условии ветвления заменить знак отношения «больше» на «меньше», то получим нужный алгоритм. Его фрагмент показан блок-схемой на рис. 2.14.

Если в алгоритме нужно одновременно искать максимальное и минимальное значения, то соответствующие ветвления можно объединить в одном цикле. Именно так сделано в приведенной ниже программе на Паскале.

Поиск минимального (максимального) элемента массива

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

Пример программы поиска минимального элемента в массиве целых чисел.

program Primer;

const n=10;

vara:array[1..n] of integer;

Begin

for i:=2 to n do

writeln(‘минимальный элемент массива’,a[min],’, номер элемента’,min);

Задание: Дан массив целых чисел. Найти сумму элементов массива, которые делятся на 5 нацело.

Алгоритм решения задачи:

1. Попросить пользователя ввести с клавиатуры 5 чисел и записать их в массив A.

2. Присвоить переменной S значение ноль (сумма элементов, которые делятся на 5).

3. Просматривая массив, найти элементы, которые делятся на 5, т.е. при делении элемента массива на 5 остаток от деления должен равняться нулю и значение этих элементов накапливать в переменной S.

4. Вывести сумму на экран.

Блок-схема программыприведена на рисунке И.3.

Рисунок И.3 – Алгоритм программы

Листинг программы:


program Primer;

var A:array[1..10] of integer;

Begin

writeln(‘Введите 10 элементов массива’);

fori:=1 to 10 do readln(A[i]);

for i:=1 to 10 do

if A[i] mod 5=0 then S:=S+A[i];

writeln(‘Сумма элементов массива, которые делятся на 5 равна’,S);

Приложение К

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9438 — | 7438 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Мастер Йода рекомендует:  Шаблоны проектирования в JavaScript простыми словами

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Задача на поиск элемента в массиве

Условие задачи

Имеется отсортированный массив из n целых чисел, который был циклически сдвинут неизвестное число раз. Напишите код для поиска элемента в массиве. Предполагается, что массив изначально был отсортирован по возрастанию.

Пример:
Ввод: найти 5 в <15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14>.
Вывод: 8 (индекс числа 5 в массиве).

Решение

Если у вас возникла мысль о бинарном поиске, вы правы!

В классической задаче бинарного поиска х сравнивают с центральной точкой, чтобы узнать, где находится х — слева или справа. Сложность в нашем случае заключается в том, что массив был циклически сдвинут, а значит, может иметь точку перегиба. Рассмотрим, например, два следующих массива:

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

Например, если мы ищем 5 в Array1 , то посмотрим на крайний левый элемент (10) и средний элемент (20). Так как 10 Array2 мы видим, что 50 > 20, а значит, отсортирована правая половина. Мы обращаемся к середине (20) и крайнему правому элементу (40), чтобы проверить, по­падает ли 5 в рассматриваемый диапазон. Значение 5 не может находиться в правой части, а значит, его нужно искать в левой части массива.

Задача становится более сложной, если левый и средний элементы идентич­ны, как в случае с массивом <2, 2, 2, 3, 4, 2>. В этом случае можно вы­полнить сравнение с правым элементом и, если он отличается, ограничить поиск правой половиной. В противном случае выбора не остается, и придется анализировать обе половины.

Код выполняется за время O(log n), если все элементы будут разными (об оценке сложности алгоритмов вы можете прочитать в нашей статье). При большом количестве дубликатов алгоритм потребует времени O(n). Это объясняется тем, что при большом количестве дубликатов часто приходится обрабатывать обе половины массива (левую и правую).

Концептуально данная задача несложна, но написать идеальную реализацию до­статочно трудно. Не беспокойтесь, если вы допустите пару-тройку ошибок при решении этой задачи. Из-за высокого риска смещения на 1 и других второстепенных ошибок код необходимо тщательно протестировать.

Также вы можете попробовать реализовать алгоритм поиска элемента в отсортированной матрице размером MxN. Решение найдете здесь.

Поиск k-ого наименьшего элемента

Сегодня на Хабре появилась очень интересная статья, о поиске минимального (максимального) значения на отрезке в массиве. Так как статья оказалось интересной и популярной, я решил с вами поделиться ещё одним алгоритмом поиска в массиве некоторых «специальных» значений.

Наверняка каждому встречалась задача нахождения k-ого наименьшего элемента в массиве. k-ый элемент характеризуется тем, что он больше (или равен) k элементов массива и меньше или равен N-k оставшихся элементов (где N – число элементов в массиве).

Задача нахождения k-ого наименьшего элемента обычно связывается с задачей сортировки, так как очевидный метод нахождения этого элемента состоит в сортировке N элементов и выборе k-ого.

Но мы с вами пойдём немного другим путём. Я предполагаю, что читатели знают, как работает алгоритм быстрой сортировки, но на всякий случай напомню. В массиве выбирается случайный элемент x, и выполнется просмотр массива слева, пока не найдётся элемент a[i]>x, затем выполняется просмотр справа, пока не будет найден элемент a[j] =x. Описанная процедура применяется рекурсивно для левой и правой части и продолжается до тех пор, пока не будет получен полностью отсортированный массив. (Немного подробнее о эффективных алгоритмах сортировки).

Процедура разделения, используемая в быстрой сортировке, даёт потенциальную возможность находить искомый (k-ый) элемент гораздо быстрее.
Этот алгоритм работает следующим образом. На первом шаге вызывается процедура разделения с L=1 и R=N (т.е. разделение выполняется для всего массива), причём в качестве разделяющего значения x выбирается a[k]. После разделения получаются значения индексов i,j такие, что

a[h] x для всех h>j
i>j

Здесь возможны три случая:
•Разделяющее значение x оказалось слишком мало. В результате граница между двумя частями меньше нужного значения k. Тогда операцию разделения нужно повторить с элементами a[i]…a[R].

•Выбранное значение x оказалось слишком велико. Тогда операцию разделения нужно повторить с элементами a[L]…a[j].

•Элемент a[k] разбивает массив на две части в нужной пропорции и поэтому является искомым значением.

Операцию разделения нужно повторять, пока не реализуется случай 3. Этот цикл выражается следующим фрагментом (прошу прощения за Pascal, но мои ученики пока знают только его):

Если предположить, что в среднем каждое разбиение делит пополам размер части массива, в которой находится искомое значение, то необходимое число сравнений будет N+N/2+N/4+…+1=2N. Это объясняет эффективность приведённой процедуры для поиска медиан и прочих величин, а также объясняет её превосходство над простым методом, состоящем в предварительной сортировке всего массива с последующим выбором k-ого элемента (где наилучшее поведение имеет порядок N*log(N)).

Надеюсь, этот алгоритм поможет вам сделать ваши программы более эффективными и быстрыми. Спасибо за внимание.

Поиск максимального элемента в массиве

Задача

Найти максимальный элемент численного массива.

Решение

Алгоритм решения задачи:

Значения, составляющие массив, могут быть получены из разных источников: путем вызова функции random, ввода значений пользователем, считывания из файла. В программе ниже используется первый вариант.
В задачах подобного рода (поиск максиму или минимума) может быть поставлена цель, найти только 1) индекс элемента, 2) только значение или 3) и то и другое. В программе ниже используется третий вариант.
Неплохо бы, чтобы при запуске программы весь массив выводился на экран. В этом случае пользователь может оценить правильность работы программы.

  1. В переменной max_num хранится текущее максимальное значение массива, а в max_index – его позиция (индекс).
  2. В программе можно выделить две части: заполнение массива числами с выводом их на экран (первый цикл for) и непосредственно поиск максимума (второй цикл for).
  3. Перед первым циклом запускается процедура randomize для того, чтобы при каждом запуске программы значения массива были разными.
  4. Изначально делается предположение, что первый элемент массива и есть максимум. Поэтому переменной max_indexприсваивается значение 1 (т.е. указатель на первый элемент массива), а max_num – непосредственно значение, хранящееся в первой ячейке массива.
  5. Начиная со второго элемента, каждое очередное значение массива сравнивается с текущим значением max_num. В случае, если текущее значение массива больше, чем хранящиеся в max_num, происходит новое присваивание обоим переменным текущего значения и индекса.

Поиск максимума для каждого окна размера k в массиве

Учитывая массив размером n и k, как вы находите максимум для каждого смежного подмассива размера k?

Я думал о наличии массива размера k, и каждый шаг вытесняет последний элемент и добавляет новый элемент и находит максимум среди этого. Это приводит к времени работы O (nk). Есть ли лучший способ сделать это?

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

Хорошей новостью является то, что в большинстве популярных языков реализована упорядоченная структура данных, которая поддерживает эти операции для вас. С++ имеет std::set и std::multiset (вам, вероятно, нужен последний), а Java имеет TreeSet .

Вы слышали о том, как это сделать в O (n), используя dequeue.

Хорошо, что это хорошо известный алгоритм для этого вопроса в O (n).

Метод, который я рассказываю, довольно прост и требует динамического программирования и имеет временную сложность O (n).

Концепция: динамическое программирование

Алгоритм:

    N — количество элементов в массиве, а W — размер окна. Итак, номер окна = N-W + 1

Теперь разделим массив на блоки W, начиная с индекса 1.

Здесь делятся на блоки размера «W» = 3. Для ввода образца:

Мы разделились на блоки, потому что мы вычислим максимум двумя способами A.), пройдя слева направо B.), пройдя справа налево. но как?

Во-первых, перемещение слева направо. Для каждого элемента ai в блоке мы найдем максимум до тех пор, пока этот элемент ai не станет от START блока до END этого блока. Итак, здесь

Во-вторых, перемещение справа налево. Для каждого элемента ‘ai’ в блоке мы найдем максимум до этого элемента ‘ai’ , начиная с END блока до START этого блока. Итак,

Теперь нам нужно найти максимум для каждого подмассива или окна размера «W». Итак, начиная с индекса = 1 до индекса = N-W + 1.

max_val[index] = max(RL[index], LR[index+w-1]);

Симметрично, для всего индекса i , (i значение в RL[i] и LR[i+w-1] сравниваются, и максимум среди этих двух является ответом для этого подмассива.

Итак, окончательный ответ: 5 6 6 9 9 9 8 2

Сложность времени: O (n)


Код реализации:

Я попытаюсь доказать: (by @johnchen902)

Если k % w != 1 ( k не является началом блока)

В противном случае ( k — начало блока)

Динамический подход к программированию очень подробно объясняется Shashank Jain. Я хотел бы объяснить, как сделать то же самое с помощью dequeue. Ключ состоит в том, чтобы поддерживать максимальный элемент в верхней части очереди (для окна) и отбрасывать бесполезные элементы, и нам также нужно отбросить элементы, которые находятся вне индекса текущего окна.
бесполезные элементы= Если текущий элемент больше, чем последний элемент очереди, то последний элемент очереди бесполезен.
Примечание. Мы сохраняем индекс в очереди, а не сам элемент. Это будет более понятно из самого кода.
1. Если текущий элемент больше, чем последний элемент очереди, то последний элемент очереди бесполезен. Нам нужно удалить этот последний элемент. (и продолжать удалять, пока последний элемент очереди не будет меньше текущего элемента).
2. Если current_index — k >= q.front(), значит, мы выходим из окна, поэтому нам нужно удалить элемент из очереди.

Так как каждый элемент находится в очереди и выгружается с максимальной точностью 1 раз, то сложность равна O (n + n) = O (2n) = O (n).
И размер очереди не может превышать предел k. поэтому сложность пространства = O (k).

Решение O (n) времени возможно путем объединения двух классических вопросов интервью:

Создайте структуру данных стека (называемую MaxStack), которая поддерживает push, pop и max в O (1) раз.

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

Модель очереди со стеком.

Это можно сделать, используя два стека. Enqueues входят в один стек, а dequeues — от другого.

Для этой задачи нам в основном нужна очередь, которая поддерживает enqueue, dequeue и max в O (1) (амортизированном) времени.

Мы объединим два выше, путем моделирования очереди с двумя MaxStacks.

Чтобы решить вопрос, мы ставим в очередь элементы k, запрашиваем max, dequeue, enqueue k + 1-й элемент, запрашиваем max и т.д. Это даст вам максимальный размер для каждого массива размера k.

Мастер Йода рекомендует:  Представлен стабильный релиз MySQL 8.0

Я считаю, что есть и другие решения.

Я считаю, что идея очереди может быть упрощена. Мы сохраняем очередь и max для каждого k. Мы вставляем новый элемент и декауруем все элементы, которые не больше, чем новый элемент.

2) Поддерживайте два новых массива, которые поддерживают текущий макс для каждого блока k, один массив для одного направления (слева направо/справа налево).

3) Используйте молоток: предварительный процесс в O (n) времени для максимальных запросов диапазона.

1) решение выше может быть наиболее оптимальным.

Какой самый быстрый алгоритм поиска элемента с самой высокой частотой в массиве

У меня есть два входных массива X и Y. Я хочу вернуть тот элемент массива X, который встречается с самой высокой частотой в массиве Y.

Наивный способ сделать это требует, чтобы для каждого элемента x массива X я линейно искал в массиве Y его количество вхождений, а затем возвращал тот элемент x, который имеет наивысшую частоту. Вот псевдоалгоритм:

Поскольку есть два вложенных цикла, временная сложность для этого алгоритма будет O (n ^ 2). Могу ли я сделать это в O (nlogn) или быстрее?

8 ответов

Используйте ключи отображения хеш-таблицы для подсчета. Для каждого элемента в массиве сделайте как counts[element] = counts[element] + 1 или эквивалент вашего языка.

В конце, переберите соответствия в хэш-таблице и найдите макс.

В качестве альтернативы, если у вас могут быть дополнительные структуры данных, вы можете пройти массив Y, чтобы каждое число обновляло свою частоту в хеш-таблице. Это займет время O(N(Y) . Затем пройдитесь по X, чтобы найти, какой элемент в X имеет наивысшую частоту. Это займет время O(N(X)) . В целом: линейное время, и так как вы должны смотреть на каждый элемент обоих X и Y в любой реализации хотя бы один раз ( РЕДАКТИРОВАТЬ : это не совсем верно для всех случаев / всех реализаций, как указывает jwpat7 , хотя это верно в худшем случае), вы не можете сделать это быстрее, чем это.

Временная сложность распространенных алгоритмов приведена ниже:

В общем, при просмотре списка для соответствия определенным критериям вы действительно не можете добиться большего, чем линейное время. Если вам нужно отсортировать массив, я бы сказал, что придерживаться Mergesort (очень надежный), чтобы найти элемент с самой высокой частотой в массиве.

Примечание . Предполагается, что вы хотите использовать алгоритм сортировки. В противном случае, если вам разрешено использовать любую структуру данных, я бы использовал структуру типа hashmap / hashtable с постоянным временем поиска. Таким образом, вы просто сопоставляете ключи и обновляете пару ключ-значение частоты. Надеюсь это поможет.

1-й шаг: сортировка по X и Y. Предполагая, что их соответствующие длины равны m и n , сложность этого шага будет O(n log n) + O(m log m) .

2-й шаг: посчитайте каждый X i в Y и отслеживайте максимальное количество пока. Поиск X i в отсортированном Y — O(log n) . Общая сложность 2-го шага: O(m log n)

Общая сложность: O(n log n) + O(m log m) + O(m log n) или упрощенно: O(max(n,m) log n)

Сортировка слиянием на основе концепции «разделяй и властвуй» дает вам сложность O (nlogn)

Предлагаемый подход будет O (n ^ 2), если оба списка имеют длину n. Более вероятно, что списки могут быть разной длины, поэтому временная сложность может быть выражена как O (mn).

Вы можете разделить вашу проблему на две фазы: 1. Упорядочить уникальные элементы из Y по частоте. 2. Найти первый элемент из этого списка, который существует в X.

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

Вопрос по arrays, algorithm &#8211 быстрый алгоритм поиска сумм в массиве

Я ищу быстрый алгоритм:

У меня есть массив int размера n, цель состоит в том, чтобы найти все шаблоны в массиве, который
x1, x2, x3 are different elements in the array, such that x1+x2 = x3

Например, я знаю, что массив int размером 3 [1, 2, 3] тогда существует только одна возможность: 1 + 2 = 3 (рассмотрим 1 + 2 = 2 + 1)

Я думаю о реализации пар и хэш-карт, чтобы сделать алгоритм быстрым. (самый быстрый, который я получил сейчас, до сих пор O(n^2))

Пожалуйста, поделитесь своей идеей для этой проблемы, спасибо

По сути, вам нужно найти все разные суммы пар значений, поэтому я не думаю, что вы собираетесь делать что-то лучше, чем O (n 2 ). Но вы можете оптимизировать, отсортировав список и уменьшив дублирующиеся значения, затем соединяя только значение с чем-либо равным или большим, и останавливаясь, когда сумма превышает максимальное значение в списке.

Должно быть не менее O (n ^ 2), так как существует n (n-1) / 2 разных сумм, которые можно проверить на наличие других членов. Вы должны вычислить все это, потому что любая пара суммированных может быть любым другим членом (начните с одного примера и переставьте все элементы, чтобы убедить себя, что все должны быть проверены). Или посмотрите на Фибоначчи для чего-то конкретного.

Таким образом, вычисление этого и поиск членов в хеш-таблице дает амортизированный O (n ^ 2). Или используйте упорядоченное дерево, если вам нужен лучший наихудший случай.

Error: User Rate Limit Exceeded

Error: User Rate Limit Exceeded

Error: User Rate Limit Exceeded

Edit: Ответ ниже относится к версии этой проблемы, в которой вам нужен только один триплет, который складывается таким образом. Когда вам нужны все из них, поскольку потенциально имеется по крайней мере O (n ^ 2) возможных выходных данных (как указано ex0du5) и даже O (n ^ 3) в патологических случаях повторных элементов, вы не собираетесь превзойти простой алгоритм O (n ^ 2), основанный на хешировании (отображение значения в список индексов с этим значением).

Это в основномпроблема 3SUM, Без потенциально неограниченно больших элементов, наиболее известные алгоритмы примерно O(n^2) , но мы только доказали, что это не может быть быстрее, чем O(n lg n) для большинства моделей вычислений.

Если целочисленные элементы лежат в диапазоне [u, v] Вы можете сделать немного другую версию этого в O(n + (v-u) lg (v-u)) сFFT, Я собираюсь описать процесс преобразования этой проблемы в эту, решить ее там, а затем выяснить ответ на вашу проблему на основе этого преобразования.

Проблема, которую я знаю, как решить с помощью FFT, состоит в том, чтобы найти арифметическую последовательность длины 3 в массиве: последовательность a , b , c с c — b = b — a или, что то же самое, a + c = 2b .

К сожалению, последний этап преобразования не так быстр, как мне бы хотелось, но я расскажу об этом, когда мы туда доберемся.

Давайте назовем ваш исходный массив X , который содержит целые числа x_1, . x_n , Мы хотим найти индексы i , j , k такой, что x_i + x_j = x_k .

Find the minimum u and maximum v of X in O(n) time. Let u’ be min(u, u*2) and v’ be max(v, v*2) .

Construct a binary array (bitstring) Z of length v’ — u’ + 1 ; Z[i] will be true if either X or its double [x_1*2, . x_n*2] contains u’ + i . This is O(n) to initialize; just walk over each element of X and set the two corresponding elements of Z .

As we’re building this array, we can save the indices of any duplicates we find into an auxiliary list Y . Once Z is complete, we just check for 2 * x_i for each x_i in Y . If any are present, we’re done; otherwise the duplicates are irrelevant, and we can forget about Y . (The only situation slightly more complicated is if 0 is repeated; then we need three distinct copies of it to get a solution.)

Now, a solution to your problem, i.e. x_i + x_j = x_k , will appear in Z as three evenly-spaced ones, since some simple algebraic manipulations give us 2*x_j — x_k = x_k — 2*x_i . Note that the elements on the ends are our special doubled entries (from 2X ) and the one in the middle is a regular entry (from X ).

Consider Z as a representation of a polynomial p , where the coefficient for the term of degree i is Z[i] . If X is [1, 2, 3, 5] , then Z is 1111110001 (because we have 1, 2, 3, 4, 5, 6, and 10); p is then 1 + x + x 2 + x 3 + x 4 + x 5 + x 9 .

Now, remember from high school algebra that the coefficient of x c in the product of two polynomials is the sum over all a, b with a + b = c of the first polynomial’s coefficient for x a times the second’s coefficient for x b . So, if we cons >2 , the coefficient of x 2j (for a j with Z[j] = 1 ) will be the sum over all i of Z[i] * Z[2*j — i] . But since Z is binary, that’s exactly the number of triplets i,j,k which are evenly-spaced ones in Z . Note that (j, j, j) is always such a triplet, so we only care about ones with values > 1.

We can then use a Fast Fourier Transform to find p 2 in O(|Z| log |Z|) time, where |Z| is v’ — u’ + 1 . We get out another array of coefficients; call it W .

Loop over each x_k in X . (Recall that our desired evenly-spaced ones are all centered on an element of X , not 2*X .) If the corresponding W for twice this element, i.e. W[2*(x_k — u’)] , is 1, we know it’s not the center of any nontrivial progressions and we can skip it. (As argued before, it should only be a positive integer.)

Otherwise, it might be the center of a progression that we want (so we need to find i and j ). But, unfortunately, it might also be the center of a progression that doesn’t have our desired form. So we need to check. Loop over the other elements x_i of X , and check if there’s a triple with 2*x_i , x_k , 2*x_j for some j (by checking Z[2*(x_k — x_j) — u’] ). If so, we have an answer; if we make it through all of X without a hit, then the FFT found only spurious answers, and we have to check another element of W .

This last step is therefore O(n * 1 + (number of x_k with W[2*(x_k — u’)] > 1 that aren’t actually solutions)), which is maybe possibly O(n^2) , which is obviously not okay. There should be a way to avoid generating these spurious answers in the output W ; if we knew that any appropriate W coefficient definitely had an answer, this last step would be O(n) and all would be well.

I think it’s possible to use a somewhat different polynomial to do this, but I haven’t gotten it to actually work. I’ll think about it some more.

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