Поиск максимума и минимума

Yashin_Sergey
Значит я сейчас что - то не дотягиваю - надо подумать, но результат сильный.

 

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

 

Всё верно, у меня в массиве ценовые котировки рынка, а это в общем случае детерминированный случайный процесс.

 

Если строить дерево а потом просто брать минимум и максимум то получится не просто медленно а очень медленно.
Так как для каждого эелементе мы выполняем несколько операций а не одну единственную операцию сравнения.
Дерево то потом не нужно.

 

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

 

объясните, пожалуйста, как же выигрыш получаеться, ведь под перебор подпадают все элементы - приведите пример кода, пожалуйста, желательно на с++.
------------------------------------------------------------------
Заранее благодарен.

 

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

 

Yashin_Sergey
так все же -все элементы перебираются?

 

Если нужно перебрать эелементы заново то конечно каждый из 10 тыс.

 

Yashin_Sergey
насколько я понял: сначала находим мин./макс. первого сегмента, а затем эти экстремумы сравниваем с элементами других сегментов, но ведь количество сравнений тоже самое.

 

Народ, а о чем собственно спор? Кто-то может найти минимум из N элементов меньше чем N-1 сравниванием?

 

1. находим мин. макс.
2. переходим к новому элементу.
3. вышли прошлые мин. или макс. за границу плавающего окна ?
3.1 вышли: заново находим мин. макс. из 10 тыс. соседних элементов.
3.2 не вышли: сравниваем новый элемент: больше макс. значит это новый макс., меньше мин. значит это новый мин.


за счет того что массив - случайный набор чисел, то пункт 3.2. выполняется чаще так как мин. и макс. не всегда находятся в конце плавающего окна.

Подробнее некуда.

 

Оказывается, что не всегда нужно делать N сравнений, а достаточно одного.

 

Yashin_Sergey
странный алгос: если мин./макс. не вышел за границу - это не значит, что старые экстремумы действительны.
например, возьмём массив: 3, 7, 5, 3, 1; длина окна: 4

1. содержимое окна: 3, 7, 5, 3.
2. содержимое окна: 7, 5, 3, 1.

экстремумы старые не вышли за границу, но нижний на втором шаге не законен.

 

не легче ли экстремумы для сегментов набирать по мере поступления данных?

 

И где в этом примере алгоритм ошибется ?

1. содержимое окна: 3(1), 7(2), 5(3), 3(4). - макс = 7(2), мин = 3(4)
2. содержимое окна: 7(2), 5(3), 3(4), 1(5). - макс = 7(2), мин = 1(5) (так как 3(4) не вышел за границу окна то сравниваем минимум с новым элементом т.е. 1(5), меньше ? значит мин = 1(5))

Если даже брать за минимум 3(1) то на след. шаге (2) 3(1) выйдет за границу и тут уже перебираем каждый элемент,
и минимум будет равен 1(5) всё равно.

Так сработает алгоритм. В чем вопрос ?

 

Смотря для каких данных.

Так можно делать если данные представленны в виде a, b, c, d где a < b, b < c, c < d и т.п.
То если окно плавающее то максимумом будет в любом случае следующий элемент, и минимумом будет последний элемент окна.
Если же окна нет то минимум будет всегда первый элемент а максимумом последний т.е. минимум "a" и максимум "d".

Если данные представленны как случайный набор чисел то способ только описанный в этой теме или простой перебор каждого элемента на каждом шаге.

 

Есть такая структура данных, как дерево отрезков. Она решает эту задачу за O(n\log(m)) в худшем случае, где n - число чисел, m - длина интервалов, на которых нужно искать максимум.

В данном случае возможна упрощенная ее реализация: считаем максимумы для всех отрезков длины 2^k, 2^k<m. Максимум на отрезке 2^k можно найти за O(1) через максимумы на отрезках длины 2^{k-1}. После чего отрезки длины m представляем как объединение двух отрезков длины 2^k (пересекающихся, если m не степень двойки) и находим максимумы для отрезков длины m за O(1) для каждого.

 

Yashin_Sergey

ага, получается, что внутрений цикл перебора сегмента врубается лишь изредка, ну, что ж признаю алгос IT' S COOOOOOOOO..OOL, но его можно улучшить - зачем сегмент перебирать весь, экстремум может выплыть из окошка, например, на середине сегмента.

 

Если он выплывет на середине окошка то это значит что новый экстремум - в начале окна.