Snaky (29.10.2009 02:43, просмотров: 152) ответил Alex B. на Как найти медиану, не сортируя массив (не меняя порядок элементов) и не используя вспомогательный массив?
функции в мат-пакетах делают через сортировку, т.к. это быстрее получается. если хочется без сортировки, то можно только итерационным приближением: 1. выбрать примерное значение медианы M (более-менее близкое к среднему)
2. Ввести вспомогательную переменную Q и обнулить ее для начала
3. Пробежаться циклом по массиву инкрементируя Q каждый раз как встретится член массива больше M.
4. Q = Q<<1.
5. Если Q > размера массива, то уменьшить M и повторить сначала, если Q <размера массива, то увеличить M и повторить сначала.
6. Условием выхода из цикла является Q == размер исходного массива (+/- допустимое отклонение).
Недостатки такого метода:
- возможно бОльшее время поиска, чем при способе с сортировкой;
- время не гарантировано (зависит от того наскольо удачно выбрано первое приближение);
- результатом будет наилучшее приближение к медиане для заланного отклонения.
Достоинство только одно:
- экономится память в обмен на выч. мощности.
DRC придумали трусы