найти медиану с минимальным временем в массиве

Question

У меня есть массив позволяет сказать a = { 1,4,5,6,2,23,4,2}; теперь я должен найти медиану позиции массива от 2 до 6 (нечетных общих терминов), так что я сделал, я принял a[1] к a[5] в arr[0] до arr[4], тогда я его отсортировал и напишу arr[2] в качестве медианы.

Но здесь каждый раз, когда я ввожу значения из одного массива в другой, так что значения моего исходного массива остаются такими же. во-вторых, я отсортировал, поэтому эта процедура занимает довольно много **time**. Так что я хочу знать, есть ли способ, которым я могу это сделать по-другому, до less my computation time.

Любые сайты, материалы для понимания, что и как делать?

Answer 1

Если вы делаете несколько запросов на одном массиве, то вы можете использовать сегмент дерева. Обычно они используются для выполнения минимальных/максимальных значений диапазона и запросов суммы диапазона, но вы можете изменить его, чтобы сделать медианный диапазон.

Дерево сегментов для набора с n интервалами использует память O (n log n) и может быть построено в O (n log n) времени. Запрос диапазона может быть выполнен в O (log n).

Пример медианы в сегменте диапазона дерева:

Вы построить дерево сегмента снизу вверх (обновление сверху вниз):

    [5] 
     [3]      [7] 
[1,2]  [4]   [6]   [8] 
1  2  3  4  5  6  7  8 

Индексы охватываемые узла:

    [4] 
     [2]      [6] 
[0,1]  [3]   [5]   [7] 
0  1  2  3  4  5  6  7 

Запрос для медианы для диапазонных индексов 4-6 будет идти по этому пути значений:

    [4] 
          [5] 
0  1  2  3  4  5  6  7 

Выполнение поиска медианы, вы знаете, сколько элементов в запросе (3), а медиана в этом диапазоне будет вторым элементом (индекс 5). Таким образом, вы по существу выполняете поиск для первого узла, который содержит этот индекс, который является узлом со значениями [1,2] (индексы 0,1).

Выполнение поиска медианы диапазона 3-6 немного сложнее, потому что вам нужно искать два индекса (4,5), которые попадают в один и тот же узел.

    [4] 
           [6] 
          [5] 
0  1  2  3  4  5  6  7 

Segment tree

Range minimum query on Segment Tree

Answer 2

Среднее значение без сортировки в O (n) раз; алгоритмы, которые делают это, называются selection algorithms.

Answer 3

Чтобы найти медиану массива из менее чем 9 элементов, я считаю, что наиболее эффективным является использование алгоритма сортировки, такого как insertion sort. Сложность плохая, но для такого небольшого массива из-за k в сложности лучших алгоритмов, таких как quicksort, сортировка вставки очень эффективна. Сделайте свой собственный тест, но я могу сказать, что у вас будут лучшие результаты с сортировкой вставки, чем с сортировкой оболочки или быстрой сортировкой.

Answer 4

Использование std::nth_element из <algorithm>, который O (N):

nth_element(a, a + size/2, a + size); 
median = a[size/2]; 

Answer 5

Я думаю, что лучший способ заключается в использовании алгоритма выбора алгоритма подсчета к-й наибольшего элемента массива. Вы можете найти общую идею алгоритма здесь: Median of Medians in Java, по википедии: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm или просто просматривать Интернет. Во время реализации могут быть сделаны некоторые общие улучшения (во время выбора медианы конкретных массивов избегайте сортировки). Однако обратите внимание, что для массива из менее чем 50 элементов его более эффективно использовать вставку сортировки, чем медиану алгоритма медианов.