задача по сортировке

[Invisible]

Задача:
есть массив A[i]
надо написать алгоритм который находит K элементов ближайших к медиане (Median)
алгоритм должен выполняться за линейное время
К - какое то заранее заданное значение.

Мне кажется надо решать так:
Вычисляем |A[i]-Median|
и заносим значения в этот же массив
A[1]=|A[1]-Median|;
A[2]=|A[2]-Median|;
.
.
.
A[n]=|A[n]-Median|;

на сколько я сколько я помню линейное время это O(n)
теперь если я начну делать сортировку уже нового массива каким то способом
(и в нем первые К элементов будут искомые)
то это уже будет больше чем O(n)
или есть алгоритмы сортировки которые работают за линейное время?

[PAV]

Почитайте эту тему, там по сути та же задача обсуждалась

[esperanto]

Ответ:

1) находим следующие порядковые статистики массива X(n/2), X(n/2-k), X(n/2+k). это делается за линейное время.

2) Стоим новый массив S, из элементов исходного массива которыe больше чем X(n/2-k) и меньше чем X(n/2+k).

3)Из S строим новый массив s=abs( s-x(n/2) ).

4) В новом массиве находим порядковую статистику S(K)

5) Все элементы нового массива меньшие найденной порядковой статистики есть прообразы необходимых к элементов наиболее близкиз к медиане.

Алгоритм линейный, от к не зависит.

Добавлено спустя 7 минут 48 секунд:

Re: задача по сортировке

Invisible писал(а):

или есть алгоритмы сортировки которые работают за линейное время?

НЕТ. в общем случаел невозможно сделать сортировку за линейное время.

[Invisible]

esperanto спасибо, но я не очень понял идею

Цитата:

1) находим следующие порядковые статистики массива X(n/2), X(n/2-k), X(n/2+k). это делается за линейное время.

что нам это дает?

Цитата:

Стоим новый массив S, из элементов исходного массива которыe больше чем X(n/2-k) и меньше чем X(n/2+k).

а что насчет чисел
которые не входят в промежуток X(n/2-k) ... X(n/2+k)
почему мы их не считаем

Цитата:

4) В новом массиве находим порядковую статистику S(K)

то есть у нас уже упорядоченный массив ?

[esperanto]

Invisible писал(а):

esperanto спасибо, но я не очень понял идею

Цитата:

1) находим следующие порядковые статистики массива X(n/2), X(n/2-k), X(n/2+k). это делается за линейное время.

что нам это дает?

Цитата:

Стоим новый массив S, из элементов исходного массива которыe больше чем X(n/2-k) и меньше чем X(n/2+k).

а что насчет чисел
которые не входят в промежуток X(n/2-k) ... X(n/2+k)
почему мы их не считаем

Цитата:

4) В новом массиве находим порядковую статистику S(K)

то есть у нас уже упорядоченный массив ?

1) Теорема: ближайшие к медиане "к" элементов, лежат между следующими порядковыми статистиками: X(n/2-k) X(n/2+k). Теорема очевидна.

2) числа которые не входят в промежуток по теореме 1 нам не интересны.

3) У нас нет упорядоченного массива, он нам и не нужен ибо порядковые статистикп находимы за линейное время.

успехов.

[Invisible]

Цитата:

1) Теорема: ближайшие к медиане "к" элементов, лежат между следующими порядковыми статистиками: X(n/2-k) X(n/2+k). Теорема очевидна.

теорема очевидна, но я ищу значения элементов которые близки по значению к A[n/2]
а не просто элементы ближайшие по расстоянию но не значению элементов

или я чего то не понимаю

[esperanto]

Invisible писал(а):

Цитата:

1) Теорема: ближайшие к медиане "к" элементов, лежат между следующими порядковыми статистиками: X(n/2-k) X(n/2+k). Теорема очевидна.

теорема очевидна, но я ищу значения элементов которые близки по значению к A[n/2]
а не просто элементы ближайшие по расстоянию но не значению элементов

или я чего то не понимаю

Что бы вас стало понятней.

Пусть дан массив 1,2,3,4,5 100,101,102,103
к=3

Какой ответ вы ожидаете:
3,4,5 - мой алгоритм
или 4,5,100

[Invisible]

esperanto так вы взяли отсортированный массив

давайте возьмем допустим
7, 9, 1, 5, 10, 15, 3, 110, 7
к=3

новый массив S, из элементов исходного массива которыe больше ч
идем по вашему алгоритму

Цитата:

1) находим следующие порядковые статистики массива X(n/2), X(n/2-k), X(n/2+k). это делается за линейное время.

X(n/2)=10
X(n/2-k)=9
X(n/2+k)=110

Цитата:

Стоим новый массив S, из элементов исходного массива которыe больше чем X(n/2-k) и меньше чем X(n/2+k).

9, 1, 5, 10, 15, 3, 110

Цитата:

3)Из S строим новый массив s=abs( s-x(n/2) ).

1, 9, 5, 0, 5, 7, 100

Цитата:

4) В новом массиве находим порядковую статистику S(K)

получается например первый и последние элементы подошли бы
как самые близкие к медиане ?
а мы их исключили, они не вошли в промежуток

[esperanto]

понятно

я написал порядковая статистика X(n/2)

согласно определению это медиана.


Определение: к-той порядковой статистикой назовем элемент исходного массива, который при упорядочивании массива по возрастанию, займет место номер к. Обозначают к-ю порядковую статистику как Х(к) только (к) должно быть в нижнем регистре.


Пересмотрите мной сказанное в контексте определения и все встанет на свои места.

с уважением

Добавлено спустя 3 минуты 47 секунд:

в этом примере:

7, 9, 1, 5, 10, 15, 110,
к=3

X(n/2)=9