Re: Минимаксная " сортировка"

From

Oleg I. Khovayko ()

To

Valentin Davydov

Date

2003-01-10T17:10:16Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

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 это не есть здорово. Но если все же интересно - 
спрашивайте, будем думать (идеи покамест недооформившиеся)...

-- 
#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)