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

UbIvItS
Числа в массиве b упорядочены - но это не числа из массива a, а функция от них. Массив b упорядочен по определению всегда. Но, к сожалению, этот алгоритм для сортировки не годится.

 

Поправьте меня, пожалуйста, если я не прав. Помоему алгоритм (O(N)) который описал Black_mirror не учитывает выход минимума из окна ?

 

Yashin_Sergey
В нем все правильно - я его добавил в тестовую прогу, а она проверяет результат работы, и если что не так, пишет, в какой позиции ошибка. Выход минимума и всех остальных элементов учитывается - смотри внимательно на объявление массива b и работу с ним.

 

UbIvItS
А причем здесь сортировка ? При сортировке необходимо упорядочить все элементы, т.е. произвести сравнение каждого с каждым. А здесь задача поиска максимума, при которой достаточно призвести сранение каждого элемента с одним текущим значением Max, т.е. это в принципе задача сложности O(N) и единственная хитрость тут - как для скользящего окна использовать результаты предыдущих сравнений, не пересчитывая все заново.

Ассимптоические сложности типа O(N) учитывают только число неких абстрактных шагов, необходимых для выполнения алгоритма. Но в разных алгосах число операций и затраты времени на каждый шаг могут быть разными. Например, если за x=1 взять операцию if a > max then max:=a, то для гениального алго Black_mirror'а будем иметь x=3, т.е. 3 операции сравнения в пересчете на один элемент, т.е. относительные затраты времени на поиск максимума будут ~3*N по сравнению с тупым перебором ~N*N. А для двоичных куч и деревьев будет ~x*N*log(M), где x > 2 из-за необходимости перестройки дерева при удалении старого элемента + нехилые доп.затраты времени, обусловленные железом (бОльшим объемом памяти, нелинейным доступом к кэшу и т.п.)

PS: застрял на предыдущей странице, а тут уже столько всего понаписали

 

Yashin_Sergey

Учитывает. Именно для этого и используется массив частичных минимумов b. На каждом шаге i=k*M+j вычисляется текущий минимум m на интервале k*M..k*M+j и в качестве результата берется Min(m,b[j]), где b[j] = min на интервале k*(M-1)+j..k*M. Массив b полностью пересчитывается при i=k*M. Все четко, просто и изящно

 

Black_mirror

Просто удивительный алгоритм.
Нет слов.

 

Yashin_Sergey
Ему самое место в "Programming Pearls" рядом с линейным алгоритмом нахождения подмассива с максимальной суммой элементов.

 

в массиве b выстраиваются минимумы - разве они не должны идти в порядке возратания??

 

UbIvItS
У меня получилось, что b[0]<=b[1]<=...<=b[M-1]. Так что все в порядке. Да и из алгоритма построения это следует.

 

Atlantic

в этой функи только операция сравнения и присваивания, а, стало быть, там числа из массива.

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

 

UbIvItS
f(A[0], ..., A[M - 1])=min(A[0], ..., A[M - 1]) всегда будет равна какому-то числу из массива. Но толку от этого мало:

Массив A: 9 8 7 6 5 4 3 2 1 0, размер окна = 3. Тогда массив b[0]=b[1]=b[2]=7. И как ты это используешь для сортировки?

 

Atlantic
по идее должно быть: b[0]=7, b[1]=8, b[2]=9.
на втором шаге текущий мин. b[1]=8 должен сравниваться с новым элементом. так где логика: массив должен быть отсортирован, но меня убеждают, что всё это дело для сортировки не годится - я с этим не спорю - почему не годится об этом было сказано ранее). но факт остаётся: здесь нужен отсортированный массив, дабы из него выуживать текущий мин., более того, массив b должен на каждом шаге перестраиваться - новый элемент может быть текущим минимумом.
------------------
c минимумами ошибся) но суть остаётся прежней.

 

Atlantic

Это точно.

Я только сейчас разобрался в чем смысл.
Настолько гениально и просто оказалось.

 

Yashin_Sergey

что точно??

 

UbIvItS

см. #207

 

Yashin_Sergey
пока я в этом сомневаюсь) - на топик #212 я ответа не получил.

 

UbIvItS
Ответ на #212:
Массив b заполняется с конца, так что:
b[2]=min{7}=7
b[1]=min{8,7}=7
b[0]=min{9,8,7}=7

Массив b не должен на каждом шаге перестраиваться - при поиске минимума в окне используется его часть (последние M-j элементов) и минимум среди тех элементов, которые не попали в эту часть - число m.

 

UbIvItS

Он работает, я тоже сомневался т.к. на взгялд решение было очень простое, но в нем прослеживается
очень интересное свойство, когда окно передвигается на след. элемент, то прошлое окно "как бы" на один сузилось,
и стало не 4 а 3, и тут у нас есть массив с мин. за 3 соседних элемента (т.к. четвертый у нас не в счет), а дальше всё просто - для того что бы получить текущий мин. нам нужно мин. за 3 последних элемента сравнить с новым элементом,
вот и всё, если новый меньше то это новый минимум, если новый не меньше то минимум = b[1]. Если окно передвинулось на 2 элемента то берем мин. за 2 соответственно, а что бы понять мин. это или нет, у нас "копится" минимальный минимум из новых элементов а для этого массив уже не нужен. Т.е. всё круто
Этот алгоритм можно сделать и без вложенного цикла, как мне кажется, я сейчас думаю над этим.

 

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

 

Массив: 1 36 81 7 8 5 14 13 2 1
Размер окна = 3

Начало: заполняем массив b: b=[1,36,81].

1) 1 36 81 7 8 5 14 13 2 1
---^----^
массив b: b=[1,36,81], m=81, текущий минимум = min(b[0], m) = min(1,81) = 1

2) 1 36 81 7 8 5 14 13 2 1
-----^----^
массив b: b=[36,81], m=min(m,7)=min(81,7)=7, текущий минимум = min(b[1], m) = min(36,7) = 7

3) 1 36 81 7 8 5 14 13 2 1
--------^---^
массив b: b=[81], m=min(m,8)=min(7,8)=7, текущий минимум = min(b[2], m) = min(81,7) = 7.

4) 1 36 81 7 8 5 14 13 2 1
----------^---^
массив b: b=[] - опустошен, заполняем его: b=[5,5,5]
b[5,5,5], m=5, текущий минимум = min(b[0], m) = min(5,5) = 5.

5) 1 36 81 7 8 5 14 13 2 1
------------^---^
массив b: b[5,5], m=min(m,14)=min(5,14)=5, текущий минимум = min(b[1], m) = min(5,5) = 5.

6) 1 36 81 7 8 5 14 13 2 1
--------------^----^
массив b: b[5], m=min(m,13)=min(5,13)=5, текущий минимум = min(b[2], m) = min(5,5) = 5.

7) 1 36 81 7 8 5 14 13 2 1
-----------------^---^
массив b: b[], заполняем b: b=[2,2,2]
массив b: b=[2,2,2], m=2, текущий минимум = min(b[0], m) = min(2,2) = 2.

8) 1 36 81 7 8 5 14 13 2 1
-------------------^---^
массив b: b=[2,2], m=min(m,1)=min(2,1)=1, текущий минимум = min(b[1], m) = min(2,1) = 1.