) навеяла.
К>Дано: массив чисел. К>Найти: К>- минимум и максимум К>- медиану К>за как можно меньшее время.
К>Очевидно, что для нахождения минимума ИЛИ максимума требуется N-1 сравнений. К>То есть, лобовое решение для минимума И максимума — 2N-2.
К>Лобовое решение для медианы, с модификацией массива — это O(N log N) : быстрая сортировка, затем берём [N/2]-й элемент.
К>Попробуйте улучшить
К>PS. Те, кто знает готовые ответы — не спешите. Это же этюд
Готового ответа не знаю, предлагаю сделать так:
1. быстрая сортировка
2. Нахождение медианы
3. Нахождение минимума и максимума (берем первый и последний элементы).
Здравствуйте, crackoff, Вы писали:
К>>Найти: К>>- минимум и максимум К>>- медиану К>>за как можно меньшее время.
C>Готового ответа не знаю, предлагаю сделать так: C>1. быстрая сортировка C>2. Нахождение медианы C>3. Нахождение минимума и максимума (берем первый и последний элементы).
Маленькая поправка: отдельно найти минимум и максимум, и отдельно найти медиану (заодно можно минимум и максимум).
Но даже если всё вместе, то твоё решение можно ускорить примерно в два раза.
) навеяла.
К>Дано: массив чисел. К>Найти: К>- минимум и максимум К>- медиану К>за как можно меньшее время.
К>Очевидно, что для нахождения минимума ИЛИ максимума требуется N-1 сравнений. К>То есть, лобовое решение для минимума И максимума — 2N-2.
К>Лобовое решение для медианы, с модификацией массива — это O(N log N) : быстрая сортировка, затем берём [N/2]-й элемент.
К>Попробуйте улучшить
К>PS. Те, кто знает готовые ответы — не спешите. Это же этюд
Применять сортировку чтибы найти медиану -- ето стрельба из пушек по воробьям. Есть линейный алгоритм, но у него сложность по-моему 20N, так что на фоне етого 2N-2 на поиск Min&Max теряются.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, crackoff, Вы писали:
К>>>Найти: К>>>- минимум и максимум К>>>- медиану К>>>за как можно меньшее время.
C>>Готового ответа не знаю, предлагаю сделать так: C>>1. быстрая сортировка C>>2. Нахождение медианы C>>3. Нахождение минимума и максимума (берем первый и последний элементы).
К>Маленькая поправка: отдельно найти минимум и максимум, и отдельно найти медиану (заодно можно минимум и максимум).
а зачем тут что то сортировать?
за один проход ищем максимум и минимум используя две дополнительные переменные
делим сумму на два
за второй проход ищем наиболее приближенный к середине элемент.
итого 2N сравнений
зы: если за медиану считать среднеарифметическое значение от всего массива то в процессе поиска минимума и максимума заодно посчитать сумму.
Здравствуйте, _JoKe_, Вы писали:
_JK>Здравствуйте, Кодт, Вы писали:
_JK>а зачем тут что то сортировать? _JK>за один проход ищем максимум и минимум используя две дополнительные переменные _JK>делим сумму на два _JK>за второй проход ищем наиболее приближенный к середине элемент.
_JK>итого 2N сравнений
_JK>зы: если за медиану считать среднеарифметическое значение от всего массива то в процессе поиска минимума и максимума заодно посчитать сумму.
_JK>возможно можно и быстрей надо подумать
А если массив будет, скажем, такой:
-3
1000000
-1
9
4
Медиана тут, очевидно, 4.
Я пока не представляю себе, как это сделать без сортировки.
Мне тутт по аське товарищ подсказал, что можно использовать более быструю поразрядную сортировку, но я думаю (сижу и думаю), как получить более изящное решение.
C>А если массив будет, скажем, такой: C>-3 C>1000000 C>-1 C>9 C>4
C>Медиана тут, очевидно, 4.
C>Я пока не представляю себе, как это сделать без сортировки. C>Мне тутт по аське товарищ подсказал, что можно использовать более быструю поразрядную сортировку, но я думаю (сижу и думаю), как получить более изящное решение.
если это иметь ввиду под медианой то не вопрос за O(n*log(n)) ищется по такому же алгоритму как быстрая сортировка только без перестановок.
C>>Я пока не представляю себе, как это сделать без сортировки. C>>Мне тутт по аське товарищ подсказал, что можно использовать более быструю поразрядную сортировку, но я думаю (сижу и думаю), как получить более изящное решение.
_JK>если это иметь ввиду под медианой то не вопрос за O(n*log(n)) ищется по такому же алгоритму как быстрая сортировка только без перестановок.
а еще в догонку вспомнил есть алгоритм нахождения такой медианы за линейное время это там где делится на части по 5 элементов ищется в них медиана потом они опять объединяются по 5 и т.д.
Здравствуйте, crackoff, Вы писали:
C>Я пока не представляю себе, как это сделать без сортировки. C>Мне тутт по аське товарищ подсказал, что можно использовать более быструю поразрядную сортировку, но я думаю (сижу и думаю), как получить более изящное решение.
Поразрядная — не всегда приемлема. Например, для вещественных чисел (хотя, если докопаться до битового представления — то несложно: мантисса, затем порядок, затем знак), а тем более — для типов, над которыми определено только отношение порядка.
Кстати сказать, radix sort выполняется за время O(Count * log(Range)), где Count — размер массива, Range — диапазон значений типа.
Т.е., она будет эффективнее быстрой сортировки — O(Count * log(Count)) — когда размер массива соразмерен или гораздо больше мощности типа.
Утрируя: массив из 100 32-битных "всех-нулей" и "всех-единиц" будет поразрядно отсортирован за 3200 проверок, тогда как быстрая сортировка расправится с ним за 99.
Здравствуйте, Кодт, Вы писали:
К>Дано: массив чисел. К>Найти: К>- минимум и максимум К>- медиану К>за как можно меньшее время. К>Очевидно, что для нахождения минимума ИЛИ максимума требуется N-1 сравнений. К>То есть, лобовое решение для минимума И максимума — 2N-2. К>Лобовое решение для медианы, с модификацией массива — это O(N log N) : быстрая сортировка, затем берём [N/2]-й элемент.
Тут полная сортировка не нужна — достаточно только одного первого прохода qsort — после этого в середине окажется медиана
(все элементы левее — меньше её, все элементы правее — больше).
Здравствуйте, _JoKe_, Вы писали:
_JK>а еще в догонку вспомнил есть алгоритм нахождения такой медианы за линейное время это там где делится на части по 5 элементов ищется в них медиана потом они опять объединяются по 5 и т.д.
Могу предположить, что это неправильный алгоритм: если на первом этапе мы отбрасываем хоть один элемент из любого подмассива, то можно принять меры, чтобы была отброшена именно медиана массива.
Здравствуйте, PinkPanther, Вы писали:
PP>Здравствуйте, Кодт, Вы писали:
PP>Тут полная сортировка не нужна — достаточно только одного первого прохода qsort — после этого в середине окажется медиана PP>(все элементы левее — меньше её, все элементы правее — больше).
Точно. А потом из левой половины находим наименьшее, а из правой — наибольшее.
Здравствуйте, PinkPanther, Вы писали:
PP>Тут полная сортировка не нужна — достаточно только одного первого прохода qsort — после этого в середине окажется медиана PP>(все элементы левее — меньше её, все элементы правее — больше).
Это если так удачно окажется, что partition мы сделаем по медиане. Иначе слева и справа от разделителя будет разное количество элементов.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, PinkPanther, Вы писали:
PP>>Тут полная сортировка не нужна — достаточно только одного первого прохода qsort — после этого в середине окажется медиана PP>>(все элементы левее — меньше её, все элементы правее — больше).
К>Это если так удачно окажется, что partition мы сделаем по медиане. Иначе слева и справа от разделителя будет разное количество элементов.
а после этого можно повторить алгоритм только для той половины в которой больше и т.д. пока не окажется что слева и справа одинаковое количество..
Здравствуйте, crackoff, Вы писали:
PP>>Тут полная сортировка не нужна — достаточно только одного первого прохода qsort — после этого в середине окажется медиана PP>>(все элементы левее — меньше её, все элементы правее — больше).
C>Точно. А потом из левой половины находим наименьшее, а из правой — наибольшее.
Если подобным способом пользоваться для поиска только минимума/максимума, то получим 2N-3 сравнений. За N-1 выполняется partition, потом за N-2 в каждом из подмассивов находим один крайний.
Чтобы растравить — у Кормена есть алгоритм поиска минимума и максимума за 1.5*N...
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, crackoff, Вы писали:
PP>>>Тут полная сортировка не нужна — достаточно только одного первого прохода qsort — после этого в середине окажется медиана PP>>>(все элементы левее — меньше её, все элементы правее — больше).
C>>Точно. А потом из левой половины находим наименьшее, а из правой — наибольшее.
К>Если подобным способом пользоваться для поиска только минимума/максимума, то получим 2N-3 сравнений. За N-1 выполняется partition, потом за N-2 в каждом из подмассивов находим один крайний.
К>Чтобы растравить — у Кормена есть алгоритм поиска минимума и максимума за 1.5*N...
int min = arr[0];
int max = arr[1];
if( min > max )
swap( &min, &max );
for( int i = 2; i < arr; ++i )
{
if( arr[i] > arr[i + 1] )
{
if( arr[i] > max ) max = arr[i];
if( arr[i + 1] < min ) min = arr[i + 1];
}
else
{
if( arr[i + 1] > max ) max = arr[i + 1];
if( arr[i] < min ) min = arr[i];
}
}
это для массива размер которого кратен 2, для любого чуть чуть еще дописать надо, я для идеи кинул она понятна поэтому дописывать не стал.
Перекуём баги на фичи!
