...
_JK>>>for( int i = 2; i < arr; ++i )
...
_JK>>>
PP>> Приведённый алгоритм выполняет 3N-1 сравнений... И при этом не считает медиану... _JK>КАК ЭТО? _JK>для каждых ДВУХ элементов массива он выполняет 3 сравнения итого сравнений — (N*3)/2 = 1.5N! _JK>медиану он и не должен был считать это ответ на строчку №1
ааа... понял почему ты так подумал это я ошибочку в коде сделал
следует читать так
_JK>>>for( int i = 2; i < arr; i+=2 )
Здравствуйте, Кодт, Вы писали:
К>Дано: массив чисел. К>Найти: К>- минимум и максимум К>- медиану К>за как можно меньшее время. К>Очевидно, что для нахождения минимума ИЛИ максимума требуется N-1 сравнений. К>То есть, лобовое решение для минимума И максимума — 2N-2. К>Лобовое решение для медианы, с модификацией массива — это O(N log N) : быстрая сортировка, затем берём [N/2]-й элемент.
Тут полная сортировка не нужна — достаточно только одного первого прохода qsort — после этого в середине окажется медиана
(все элементы левее — меньше её, все элементы правее — больше).
) навеяла.
К>Дано: массив чисел. К>Найти: К>- минимум и максимум К>- медиану К>за как можно меньшее время.
К>Очевидно, что для нахождения минимума ИЛИ максимума требуется 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.
Здравствуйте, _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, для любого чуть чуть еще дописать надо, я для идеи кинул она понятна поэтому дописывать не стал.
Здравствуйте, _JoKe_, Вы писали:
C>>>Точно. А потом из левой половины находим наименьшее, а из правой — наибольшее.
К>>Если подобным способом пользоваться для поиска только минимума/максимума, то получим 2N-3 сравнений. За N-1 выполняется partition, потом за N-2 в каждом из подмассивов находим один крайний.
К>>Чтобы растравить — у Кормена есть алгоритм поиска минимума и максимума за 1.5*N... _JK>
_JK>int min = arr[0];
_JK>int max = arr[1];
_JK>if( min > max )
_JK> swap( &min, &max );
_JK>for( int i = 2; i < arr; ++i )
_JK>{
_JK> if( arr[i] > arr[i + 1] )
_JK> {
_JK> if( arr[i] > max ) max = arr[i];
_JK> if( arr[i + 1] < min ) min = arr[i + 1];
_JK> }
_JK> else
_JK> {
_JK> if( arr[i + 1] > max ) max = arr[i + 1];
_JK> if( arr[i] < min ) min = arr[i];
_JK> }
_JK>}
_JK>
Приведённый алгоритм выполняет 3N-1 сравнений... И при этом не считает медиану...
_JK>это для массива размер которого кратен 2, для любого чуть чуть еще дописать надо, я для идеи кинул она понятна поэтому дописывать не стал.
К>>>Чтобы растравить — у Кормена есть алгоритм поиска минимума и максимума за 1.5*N... _JK>>
_JK>>int min = arr[0];
_JK>>int max = arr[1];
_JK>>if( min > max )
_JK>> swap( &min, &max );
_JK>>for( int i = 2; i < arr; ++i )
_JK>>{
_JK>> if( arr[i] > arr[i + 1] )
_JK>> {
_JK>> if( arr[i] > max ) max = arr[i];
_JK>> if( arr[i + 1] < min ) min = arr[i + 1];
_JK>> }
_JK>> else
_JK>> {
_JK>> if( arr[i + 1] > max ) max = arr[i + 1];
_JK>> if( arr[i] < min ) min = arr[i];
_JK>> }
_JK>>}
_JK>>
PP> Приведённый алгоритм выполняет 3N-1 сравнений... И при этом не считает медиану...
КАК ЭТО?
для каждых ДВУХ элементов массива он выполняет 3 сравнения итого сравнений — (N*3)/2 = 1.5N!
медиану он и не должен был считать это ответ на строчку №1
Здравствуйте, _JoKe_, Вы писали:
_JK>Здравствуйте, Кодт, Вы писали:
К>>Здравствуйте, PinkPanther, Вы писали:
PP>>>Тут полная сортировка не нужна — достаточно только одного первого прохода qsort — после этого в середине окажется медиана PP>>>(все элементы левее — меньше её, все элементы правее — больше).
К>>Это если так удачно окажется, что partition мы сделаем по медиане. Иначе слева и справа от разделителя будет разное количество элементов.
_JK>а после этого можно повторить алгоритм только для той половины в которой больше и т.д. пока не окажется что слева и справа одинаковое количество..
вот алгоритм на основе быстрой сортировки только раз нам не надо сортировать то одну половину может смело отбрасывать...
кто возьмется оценить сложность... мне кажется, при должной оптимизации кода будет около N
при желании можно сдесь и медиану найти!
так что вроде задача решена
void findmin( int* first, int* last, int** min )
{
if( last - first == 1 )
{
*min = *last<*first?last:first;
return;
}
int *l = first;
int *r = last;
int m = *(l + ((r - l)>>1) );
while( l < r )
{
while( *l < m && l < r ) ++l;
while( *r > m && r > l) --r;
swap( l,r );
}
findmin( first, l, min );
}
void findmax(int* first, int* last, int** max)
{
if( last - first == 1 )
{
*max = *last>*first?last:first;
return;
}
int *l = first;
int *r = last;
int m = *(l + ((r - l)>>1) );
while( l < r )
{
while( *l < m && l < r ) ++l;
while( *r > m && r > l) --r;
swap( l,r );
}
findmax( l, last, max );
}
void findminmax( int* first, int* last, int **min, int **max )
{
int *l = first;
int *r = last - 1;
int m = *(l + ((r - l)>>1) );
while( l < r )
{
while( *l < m && l < r ) ++l;
while( *r > m && r > l) --r;
swap( l,r );
}
findmin( first, l, min );
findmax( l, last, max );
}
Проще сказать, используем алгоритм Partition (которым пользуется QuickSort).
Если на C++ и STL, то
template<class I, class P>
I median(I begin, I end, P pred)
{
if(begin==end) return begin;
I a=begin, b, c=end;
while(true)
{
typedef std::iterator_traits<I>::difference_type diff_t;
diff_t l = std::distance(begin,b), r = std::distance(b,end);
if(l==r || l+1==r) return b; // попали точно на серединуif(l<r) // справа больше - пойдём туда
a = b,
b = std::partition(b,c,pred);
else// слева больше - пойдём туда
c = b,
b = std::partition(a,b,pred);
}
}
Кстати сказать, реализация Partition может быть достаточно хитрой, чтобы избегать потерь производительности на плохих наборах:
— с рандомизацией
— с выбором разделителя из нескольких кандидатов
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, _JoKe_, Вы писали:
К>Проще сказать, используем алгоритм Partition (которым пользуется QuickSort). К>Кстати сказать, реализация Partition может быть достаточно хитрой, чтобы избегать потерь производительности на плохих наборах: К>- с рандомизацией К>- с выбором разделителя из нескольких кандидатов
Шо то у меня такое впечатление, что можно сделать Partition ещё более хитрым, чтобы гарантированно сходиться всегда в середине — т.е.
надо после каждого шага менять местами направление... Ну в общем, с какого конца списка начинать поиск след. кандидатов на обмен — тогда не нужна рекурсия,
и это будет работать за линейное время. Т.е. итого весь алгоритм, вместе с поиском min и max работает за линейное время.
_JK>>а еще в догонку вспомнил есть алгоритм нахождения такой медианы за линейное время это там где делится на части по 5 элементов ищется в них медиана потом они опять объединяются по 5 и т.д.
К>Могу предположить, что это неправильный алгоритм: если на первом этапе мы отбрасываем хоть один элемент из любого подмассива, то можно принять меры, чтобы была отброшена именно медиана массива.
Предположение неверно: я узнал этот алгоритм. Оказывается, всё честно
Идея его — вот в чём:
Пусть худшее время нахождения медианы (и, более общо, i'го элемента — т.н. i'й порядковой статистики) в массиве из n равно T(n).
Начнём искать i'й элемент в массиве из n...
1) Разобьём массив на k = ]n/g[ групп по g элементов (g — небольшое и нечётное). Каждую отсортируем (за O(1)).
2) Соберём оттуда массив медиан, размером k и за время T(k) найдём медиану медиан X.
3) Очевидно, что массив разбивается на три части:
— заведомо меньшие, чем M: обозначены (-): n_
— заведомо большие, чем M: обозначены (+): n^
— конкуренты: все остальные (? и M): n' = ](n-k-g)/2[ + 1
4) Определим, в какую из частей попадает i и сузим поиск.
Таким образом,
T(n) <= T(k) + max{T(n_),T(n'),T(n^)} + kt,
где t — худшее время сортировки группы — некая константа.
Заметим, что x<y ==> T(x)<=T(y):
если бы это было не так, T(y)<T(x), мы могли бы дописать к массиву из x ещё y-x "бесконечно больших" фиктивных элементов и тем самым улучшить ситуацию, получив T(x)==T(y).
Поэтому max{T(n_),T(n'),T(n^)} = T(max{n_,n',n^}) = T(n').
T(n) <= T(k) + T(](n-k-g)/2[+1) + kt.
Теперь нужно доказать, что T(n) = O(n),
т.е., есть некая константа c, для которой,
начиная с некоего n=n0, T(n) <= cn.
Доказательство — по индукции.
Индуктивный переход выглядит так:
T(n)
<= T(k) + T(](n-k-g)/2[+1) + kt
--- избавимся от округления
<= T(k) + T((n-k-g)/2 + 2) + kt
<= c·(k + (n-k-g)/2 + 2) + kt
--- допустим, что c>=k
<= c·(3k/2 + n/2 — g/2 + 2)
--- избавимся от k = ]n/g[ <= n/g + 1
<= c·(3n/2g + n/2 — g/2 + 5/2)
== c·(n·(3/2g + 1/2) + 5/2 — g/2)
== c·(n·(3+g)/2g + (5-g)/2)
== cZ(n)
Осталось показать, что Z(n) <= n.
Для g=3, Z(n) = n+1 --- облом.
Для g=5, Z(n) = n
Для g>5, Z(n) = n·(3+g)/2g + (5-g)/2; {нечто<1}·n + {нечто<0}
Нижнюю границу, начиная с которой T(n) становится сублинейной, можно как-то выковырять из разворота этого неравенства. Кормен утверждает, что для g=5, n0=70. Тут уже моей соображалки сейчас не хватает (а Кормена под рукой нет).
какое-то длинное доказательство сложности. на одной из первых лекций по теории алгоритмов оценка сложности для етого алгоритма была доказана в одну строчку. Оно опирается на теорему о рекуррентных формулах. Имея ету формулу
T(n) <= T(k) + T(](n-k-g)/2[+1) + kt.
и используя ету теорему можно сразу получить коеффициент с. Для g=5 он и равен 20 на сколько я помню.
Здравствуйте, Cruelty, Вы писали:
C>какое-то длинное доказательство сложности. на одной из первых лекций по теории алгоритмов оценка сложности для етого алгоритма была доказана в одну строчку. Оно опирается на теорему о рекуррентных формулах.
Перекуём баги на фичи!
