finden Median mit einem Minimum an Zeit in einem Array

Question

Ich habe ein Array sagen lässt a = { 1,4,5,6,2,23,4,2}; jetzt muss ich Median der Feldposition von 2 bis 6 (ungerade Gesamt Begriffe) finden, also was ich getan habe, habe ich a[1]-a[5] genommen in arr[0] zu arr[4] dann habe ich es sortiert und und schreiben Sie die arr[2] als Median.

Aber hier jedes Mal, wenn ich Werte von einem Array in ein anderes eingabe, so dass die Werte meiner ursprünglichen Array bleibt gleich. zweitens habe ich sortiert, so dass diese Prozedur ziemlich viel **time** dauert. Also ich will wissen, ob es irgendeinen Weg gibt, ich kann es auf andere Weise tun als less my computation time.

Alle Websites, Material zu verstehen, was und wie zu tun?

Answer 1

Wenn Sie mehrere Abfragen auf demselben Array tun, dann können Sie einen Segmentbaum verwenden. Sie werden im Allgemeinen verwendet, um Bereichs-Minimum/Maximum- und Bereichs-Summen-Abfragen durchzuführen, aber Sie können sie ändern, um den Bereichs-Median auszuführen.

Ein Segmentbaum für einen Satz mit n Intervallen verwendet O (n log n) -Speicher und kann in O (n log n) -Zeit eingebaut werden. Eine Bereichsabfrage kann in O (log n) erfolgen.

Beispiel des medianen in Bereichssegmentbaum:

Sie bauen den Segmentbaum von unten nach oben (Update von oben nach unten):

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

Indices von Knoten abgedeckt:

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

Eine Abfrage für Median für Bereichsindizes von 4-6 würde diesen Pfad der Werte gehen:

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

Wenn Sie nach dem Median suchen, kennen Sie die Anzahl der gesamten Elemente in der Abfrage (3) und der Median in diesem Bereich wäre das zweite Element (Index 5). Sie suchen also im Wesentlichen nach dem ersten Knoten, der diesen Index enthält, der Knoten mit Werten [1,2] (Indizes 0,1) ist.

Eine Suche nach dem Median des Bereichs 3-6 ist etwas komplizierter, weil Sie nach zwei Indizes (4,5) suchen müssen, die zufällig im selben Knoten liegen.

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

Segment tree

Range minimum query on Segment Tree

Answer 2

Es ist möglich, den Median ohne Sortierung in O (n) Zeit zu finden; Algorithmen, die dies tun, heißen selection algorithms.

Answer 3

Um den Median eines Arrays aus weniger als 9 Elementen zu finden, halte ich einen Sortieralgorithmus wie Insertion sort für die effizienteste. Die Komplexität ist schlecht, aber für solch ein kleines Array wegen der Komplexität der besseren Algorithmen wie Quicksort ist Insertion Sort sehr effizient. Machen Sie Ihren eigenen Benchmark, aber ich kann sagen, dass Sie bessere Ergebnisse mit Insertion Sortierung als mit Shell-Sortierung oder Quicksort haben werden.

Answer 4

Verwenden std::nth_element von <algorithm> die O (N):

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

Answer 5

Ich denke, der beste Weg, um den Median der Mediane Algorithmus des Zählens der k-ten größte Element eines Arrays zu verwenden ist. Sie können die allgemeine Idee des Algorithmus hier finden: Median of Medians in Java, auf wikipedia: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm oder einfach im Internet surfen. Während der Implementierung können einige allgemeine Verbesserungen vorgenommen werden (vermeiden Sie die Sortierung bei der Auswahl des Medians bestimmter Arrays). Beachten Sie jedoch, dass es für ein Array mit weniger als 50 Elementen effizienter ist, die Insertion-Sortierung als Median des Median-Algorithmus zu verwenden.