|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yury Los 2:5020/400 07 Feb 2002 09:41:27
To : Pavel Fomin
Subject : Re: Hyжен алгоpитм
--------------------------------------------------------------------------------
Привет!
ну наконец-то... Ж)
> SS> Hyжен быстpый алгоpитм поиска k-того минимального элемента в
массиве
> SS> длинной n. Разyмеется, O(n^2) не катит ;), хочется что-то типа
O(nlogn)
> SS> ...
> Hу раз сортировать нельзя, то
> 1) можешь завести массив
лучше уж обозвать "стеком"
>на k элементов и заносить туда минимальные с
> вытеснением старых. Этот массив может быть отсортирован по убыванию.
гхм.. Собственно вытеснение из стека на каждом шаге, но не "старых"... Ж) а
большего на вершине стека, чем текущее тестируемуе из массива. Ж)
при такой постановке- стек сортируется по возрастанию. хотя какая зазница-
"голова,хвост" Ж)
главное - если тестируемый элемент из массива меньше максимального в стеке-
максимальное- долой и сортируем его "погружением\всплытием" Ж)
> Т.е.берешь очередной элемент данных и если в твоем массиве Ks есть
свободные места
> или этот элемент не больше самого большого, вставляешь его. После одного
> прохода по данным твой массив будет содержать k минимальных чисел, из
которых
> требуется первое.
или последнее (на вершине стека)
>Вставлять можно методом деления пополам. Сложность
> O(n*k*log(k)).
> 2) Можешь просто пройтись k раз по массиву и искать следующий минимальный.
> Сложность O(n*k).
> Я нигде не напутал?
Ж)
--- ifmail v.2.15dev5
* Origin: Taganrog Telectrocommunication Node (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
