НГУ

Форумы НГУ
Текущее время: Вс апр 21, 2019 9:25 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Медиана одномерного массива
СообщениеДобавлено: Сб авг 12, 2006 4:39 pm 
Не в сети
Редкий гость

Зарегистрирован: Вс фев 05, 2006 3:15 pm
Сообщения: 5
Откуда: Михаил
Подскажите, существуют ли специализированные алгоритмы поиска медианы в одномерном массиве.

Медиана одномерного массива A[1...n] размера n равна
A'[n/2], если n - нечетно и
(A'[n/2]+A'[n/2+1])/2, если n - четно
где A' - отсортированный массив A

Т.к. создание копии исходного массива и ее копирование - дорогие операции, особенно для больших размерностей, хотелось бы узнать, существуют ли специализированные алгоритмы поиска медианы без сортировки

На одном форуме задавал вопрос, посоветовали применить модифицированный алгоритм быстрой сортировки (т.е. сортировать только одну партицию из двух, что более эффективно).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт окт 12, 2006 4:38 am 
Не в сети
Редкий гость

Зарегистрирован: Пн сен 27, 2004 8:35 pm
Сообщения: 14
Откуда: Igor
ДА вероятностный алгоритм поиска медианы.

_________________
Когда за этим предложением не наблюдают, оно написано по немецки


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB