|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 10 Jan 2003 18:10:16
To : Valentin Davydov
Subject : Re: Минимаксная " сортировка"
--------------------------------------------------------------------------------
Valentin Davydov wrote:
>
> меньше, чем N. Тривиальный алгоритм прямого перебора линеен по N и
> квадратичен по K. Можно ли его как-нибудь ускорить?
Есть такое нехорошее подозрение, что существенно ускорить,
уйдя от K^2 - вряд ли получится.
Обьясняю почему.
Дело в том, что все более-менее быстрые алгоритмы сортировки,
использующие сравнение, исходят из транзитивности операций
"меньше/больше" (в обшем случае, эта операция определает порядок
следования элементов в выходном массиве).
To есть, предполагается, что если A < B, и
B < C, то следовательно, и A < C. Таким образом, экономится
сравнение A # C, что однако не мешает расположить результат
в правильном порядке.
В Вашем же случае сравнение явно нетранзитивно, и результат
текушего сравнения зависит от порядка выбора точек.
Пример: Есть точки:
1 2
3 4
Если в качестве начальной точки брать "1", то
выходной порядок будет 1432
Если же в качестве начальной точки брать "2", то
выходной порядок будет 2341
То есть порядок точек "34/43" зависит от предистории
выбора. Поэтому сравнение приходится делать по принципу
"каждый с каждым", то есть K^2.
Есть кое-какие идеи, как ускорить алгоритм,
отбросив часть сравниваемых точек, но тем не менее, уйти от K^2
все равно не получается.
Maло того - во всех этих идеях в той или иной мере присутствует
сортировка, или еще какая-либо "преклассификация" всех N точек.
Для K <<< N это не есть здорово. Hо если все же интересно -
спрашивайте, будем думать (идеи покамест недооформившиеся)...
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Минимаксная " сортировка"