Найти медиану параллельно

Question

Если у вас есть огромное количество цифр и сто компьютеров, как бы вы нашли медиану чисел?

Answer 1

Использовать алгоритм выбора.

1. Разделить массив чисел на 100 разделов.
2. Каждый процессор должен использовать общую сводку для разделения массива на две группы (влево / вправо)
3. тогда каждый процессор должен отправить лидеру размер этих двух групп
4. лидер должен рассчитать, какая группа меньше, и передать сообщение, чтобы избавиться от одной из этих групп.
5. возвращайтесь к шагу 2, пока не найдете медиану

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

прочитайте статью в вики - http://en.wikipedia.org/wiki/Selection_algorithm