2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 задача по сортировке
Сообщение24.11.2006, 13:00 
Задача:
есть массив 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)
или есть алгоритмы сортировки которые работают за линейное время?

 
 
 
 
Сообщение24.11.2006, 13:48 
Аватара пользователя
Почитайте эту тему, там по сути та же задача обсуждалась

 
 
 
 
Сообщение24.11.2006, 15:27 
Ответ:

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 писал(а):
или есть алгоритмы сортировки которые работают за линейное время?


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

 
 
 
 
Сообщение24.11.2006, 18:32 
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)

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

 
 
 
 
Сообщение24.11.2006, 18:36 
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) У нас нет упорядоченного массива, он нам и не нужен ибо порядковые статистикп находимы за линейное время.

успехов.

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

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

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

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

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

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


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

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

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

 
 
 
 
Сообщение24.11.2006, 19:36 
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)


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

 
 
 
 
Сообщение24.11.2006, 19:46 
понятно

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

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


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


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

с уважением

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

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

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

X(n/2)=9

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group