|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 06 Feb 2002 23:10:53
To : Stanislav Shwartsman
Subject : Hyжен алгоpитм
--------------------------------------------------------------------------------
02 Фев 02 09:13, you wrote to Sergey Semenov:
SS>> Как я понимаю, очевидный алгоpитм это: в массиве находим
SS>> минимальный, его отбpасываем, затем ищем следyющий минимальный,
SS>> его снова обpасываем и так k-pаз ... Все pавно сложность
SS>> полyчается O(n^2) :( Пpо элементы массива ничего неизвестно
SS>> :(((
SS> Читал я вас тут читал ... думал, что народ сам в конце-концов откроет
SS> Cormen 'Introduction to Algorithms' и посмотрит там решение.
SS> Цитирую:
SS> 1. Выбор за линейное время.
SS> Randomized_Select(A,p,r,i): // вернуть i по возрастанию элемент в
SS> -------------------------- // A[p...r]
SS> if(p=r) return A[p];
SS> q = Randomized_Partition(A,p,r);
SS> k = q-p+1;
SS> if(i<=k) return Randomized_Select(A,p,q,i);
SS> else return Randomized_Select(A,q+1,r,i-k);
SS> Randomized_Partition(A,p,r):
SS> ---------------------------
SS> i=random(p,r);
SS> swap(A[p],A[i]);
SS> return Partition(A,p,r);
SS> Partition(A,p,r): // элемент x=A[p] выбирается граничным
SS> ---------------- // все, что больше него -> в конец
SS> массива
SS> x=A[p]; // все, что меньше -> в начало
SS> i=p-1;
SS> j=r+1;
SS> while(true)
SS> {
SS> repeat j-- until (A[j]<=x);
SS> repeat i++ until (A[i]>=x);
SS> if(i<j) swap(A[i],A[j]);
SS> else return j;
SS> }
SS> Время работы алгоритма - в худшем случае O(n^2). In common case -
SS> O(n).
SS> Есть еще версия детерминисткая (мы ее даже в ВУЗе проходили на
SS> алгоритмах), которая всегда гарантирует O(n), но с очень большим
SS> C.
SS> То есть результат можно ждать где-то в районе 12n или 30n (в
SS> зависимости
SS> от реализации). Чтобы это стало быстрее просто сортировки надо
SS> очень
SS> постораться ;)
SS> 1. Просьба занести это в FAQ.
SS> 2. Будут вопросы - я пока тут.
Пример красивый, только этот метод быстрой сортировки весьма популярен, и в FAQ
по сортировке , коорое тут было оно есть. А задача дейтсвительно ставилась без
сортировки, точнее обычно бывает так: "исходный файл слишком велик,
промежуточные файлы создавать нельзя".
Andrey
... . у меня не жизнь, а абы чо (q) Ляпис
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
