|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 02 Feb 2002 10:13:58
To : Sergey Semenov
Subject : Hyжен алгоpитм
--------------------------------------------------------------------------------
01 Feb 02 23:24, you wrote to Michael Ryazanov:
SS> Как я понимаю, очевидный алгоpитм это: в массиве находим
SS> минимальный, его отбpасываем, затем ищем следyющий минимальный, его
SS> снова обpасываем и так k-pаз ... Все pавно сложность полyчается O(n^2)
SS> :(
SS> Пpо элементы массива ничего неизвестно :(((
Читал я вас тут читал ... думал, что народ сам в конце-концов откроет
Cormen 'Introduction to Algorithms' и посмотрит там решение.
Цитирую:
1. Выбор за линейное время.
Randomized_Select(A,p,r,i): // вернуть i по возрастанию элемент в
-------------------------- // A[p...r]
if(p=r) return A[p];
q = Randomized_Partition(A,p,r);
k = q-p+1;
if(i<=k) return Randomized_Select(A,p,q,i);
else return Randomized_Select(A,q+1,r,i-k);
Randomized_Partition(A,p,r):
---------------------------
i=random(p,r);
swap(A[p],A[i]);
return Partition(A,p,r);
Partition(A,p,r): // элемент x=A[p] выбирается граничным
---------------- // все, что больше него -> в конец массива
x=A[p]; // все, что меньше -> в начало
i=p-1;
j=r+1;
while(true)
{
repeat j-- until (A[j]<=x);
repeat i++ until (A[i]>=x);
if(i<j) swap(A[i],A[j]);
else return j;
}
Время работы алгоритма - в худшем случае O(n^2). In common case - O(n).
Есть еще версия детерминисткая (мы ее даже в ВУЗе проходили на
алгоритмах), которая всегда гарантирует O(n), но с очень большим C.
То есть результат можно ждать где-то в районе 12n или 30n (в зависимости
от реализации). Чтобы это стало быстрее просто сортировки надо очень
постораться ;)
1. Просьба занести это в FAQ.
2. Будут вопросы - я пока тут.
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
