ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergiy Kanilo                        2:5020/400     02 Feb 2002  00:52:11
 To : Mike Roschin
 Subject : Re: Hyжен алгоpитм
 -------------------------------------------------------------------------------- 
 

 "Mike Roschin" <Mike.Roschin@f243.n5030.z2.fidonet.org> wrote in message
 news:3333813905@f243.n5030.z2.ftn...
 
 >  SS>     Hyжен быстpый алгоpитм поиска k-того минимального элемента в
 >  SS> массиве длинной n. Разyмеется, O(n^2) не катит ;), хочется что-то
 >  SS> типа O(nlogn) ...
 > IMHO можно так : рожаешь дополнительный массив на пять элементов,
 
 записываешь в
 
 > него первые пять элементов исходного массива. Последовательно, начиная с
 > шестого, берешь по одноу элементу из исходного массива, проверяешь нет ли
 
 в
 
 > дополнительном такого элемента, который больше взятого и если есть -
 
 замещаешь
 
 > его новым значением. Стало быть по окончании прогона в дополнительном у
 
 тебя
 
 > будет пятерка наименьших элементов из исходного массива. Выбрать из них
 > наибольший труда не составит :). Он и будет искомым.
 > Поскольку прогон вдоль искомого только один, то порядок получается O(n).
 
 А откуда взялось 5?
 А если нужен N/2-тый элемент?
 Получается те же O(N^2).
 
 Если значения распределены более-менее равномерно, то можно
 делать так:
 1) допустим надо найти некоторое need_number значение из массива,
 2) одним проходом найдем минимальное/максимальное значения
 (min_value,max_value),
 3) среднее значение mean_value =(min_value+max_value)/2
 4) одним проходом сколько значений
 
 >=min_value и <=mean_value это будет low_count
 
 и сполько
 
 >mean_value и <=max_value это будет high_count
 
 5) если need_number<low_count, то
 max_value=mean_value
 и повторяем с 3)
 6) если need_number>low_count то
 min_value=mean_value, need_number =need_number-low_count
 и опять же на 3)
 7) если need_number==low_count то
 нужный элемент - максимальный среди <=mean_value
 
 В среднем это должно быть около O(N*logN).
 
 Для ускорения можно запоминать места первого и последнего
 элемента попадающих в [min_value,max_value], что опять же
  может дать ускорение "в среднем".
 
 Cheers,
 Serge
 
 --- ifmail v.2.15dev5
  * Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Hyжен алгоpитм   Sergiy Kanilo   02 Feb 2002 00:52:11   Hyжен алгоpитм   Mike Roschin   03 Feb 2002 19:01:07