Здравствуйте.
На предложенную задачу мало кто отреагировал. Жаль. Если не затруднит,
то напишите почему?
В этом выпуске разбор предложенной задачи. Вопросы по содержанию статьи
прошу направлять её автору.
Ищем медиану по определению Можно сделать так: считать всю последовательность из входного файла,
отсортировать её, а потом уже искать медиану по определению. Это решение
неприемлемо из-за ограничения на объём доступной памяти (не более 1000
Кб). Действительно, в худшем случае придётся хранить 250000 элементов
типа longword (unsigned long в C++), т.е. придётся расходовать по 4 байта
на каждый элемент. Всего получится ~1000000 байт. А надо ещё учесть потребление
памяти алгоритмом сортировки... В общем, явное MLE (превышение ограничения
по памяти).
От кого бы избавиться? Итак, хранить все элементы последовательности бесперспективно.
Что можно не хранить?
Пример
Ответ достаточно прост. Но может быть очевиден не всем. Поэтому
разберёмся на примере.
Пусть дана последовательность из 9-ти элементов. Ситуацию, когда ни
один из них ещё не считан, изобразим так:
?
?
?
?
?
?
?
?
?
Рассмотрим момент, когда считана "большая половина" (5 элементов)
массива:
7
5
4
2
4
?
?
?
?
Можно заметить, что в зависимости от того, какие именно 4 элемента остались,
медианой может оказаться любой из уже считанных, например, наибольший:
7
5
4
2
6
10
10
10
10
Или наименьший:
7
5
4
2
6
1
1
1
1
И, конечно, медиана может скрываться среди несчитанных элементов:
7
5
4
2
6
2
3
1
1
Но что будет, если считать на один элемент больше?
7
5
4
2
6
2
?
?
?
Можно утверждать, что наибольший из считанных элементов не может быть
искомой медианой. Даже тогда, когда все оставшиеся больше него, медианой
станет предыдущий по величине:
7
5
4
2
6
2
100
100
100
Если же не все оставшиеся больше максимального из уже считанных, медиана
может оказаться и того меньше:
7
5
4
2
6
2
3
100
100
В общем, максимальный элемент можно уже исключить из рассмотрения:
7
5
4
2
6
2
?
?
?
А дальше всё повторится. Считаем ещё один элемент:
7
5
4
2
6
2
3
?
?
И вновь окажется, что максимальный из считанных не может быть медианой:
7
5
4
2
6
2
3
100
100
Поэтому можно удалить максимальный:
7
5
4
2
6
2
3
?
?
Считаем оставшиеся два элемента, каждый раз удаляя наибольший:
7
5
4
2
6
2
3
100
?
7
5
4
2
6
2
3
100
1
Среди оставшихся элементов выбираем наибольший - он и будет искомой медианой.
7
5
4
2
6
2
3
100
1
Описание алгоритма
Из примера должно быть ясно, что для нечётного N (N>1) решать задачу
можно так:
Считать N/2+1 элементов. (знаком "/" обозначено целочисленное
деление - div в Паскале) Затем считать все оставшиеся элементы, каждый
раз после считывания удаляя наибольший из уже считанных. По окончании
этого процесса останется N/2+1 элементов, наибольший среди которых будет
искомой медианой.
Этот же алгоритм работает и при чётном N. Главное, на что надо обратить
внимание: ответом будет не наибольший из оставшихся элементов, а среднее
арифметическое двух наибольших.
Потребление памяти и время работы
Очевидно, в каждый момент времени придётся хранить не более, чем N/2+2
элемента последовательности. Поэтому, в сравнении с поиском медианы
по определению, памяти расходуется в 2 раза меньше.
Что же касается времени работы предложенного алгоритма, всё не так уж
и безоблачно. Допустим, считываемые элементы хранятся в обычном массиве.
Тогда вставка нового элемента происходит за время O(1) - мы его просто
в конец массива допишем. Удаление максимального элемента потребует времени
O(N). Действительно, перед удалением максимальный элемент ещё надо найти,
а в неотсортированном массиве это потребует просмотра всех элементов.
Количество элементов пропорционально N (в каждый момент времени придётся
хранить не больше, чем N/2+2 элементов), отсюда и получается оценка O(N).
Вставка и удаление осуществляются в цикле. Количество итераций этого цикла
также пропорционально N. Таким образом, получаем приблизительную асимптотическую
оценку времени работы всего алгоритма O(N*N), т.е. O(N^2).
Так как N довольно велико (250000 по условию задачи), такая реализация
на максимальном тесте будет работать больше 1 секунды.
Можно достичь лучшей производительности, а именно времени
работы O(N lgN). Для этого я реализовал очередь с приоритетами на основе
пирамиды, но это не единственно возможное решение.
