|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Pavel Fomin 2:5026/49.21 31 Jan 2002 03:56:23
To : Sergey Semenov
Subject : Re: Hyжен алгоpитм
--------------------------------------------------------------------------------
20 Jan 02 17:15, you wrote to All:
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).
Я нигде не напутал?
Pasha 1st, RU.(PASCAL[.SOURCES|.CHAINIK|.ASM]|ACM)
... Говорила мне мама: "Hе лезь в системщики"
--- GoldED/W32 3.0.1-asa9 SR3
* Origin: Windows имеет всех, кто ее имеет (2:5026/49.21)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
