Ich habe ein Array, sagen wir a = { 1,4,5,6,2,23,4,2};
Jetzt muss ich den Median der Array-Position von 2 bis 6 finden (ungerade Gesamtausdrücke), also was ich getan habe, habe ich a[1] auf a[5] in arr[0] auf arr[4] genommen, dann habe ich es sortiert und und schreibe die arr[2] als Median.
Aber hier jedes Mal, wenn ich Werte von einem Array in ein anderes gebe, so dass die Werte meines ursprünglichen Arrays gleich bleiben. zweitens habe ich sortiert, also nimmt diese Prozedur ziemlich viel **time** .
Also ich möchte wissen, ob es irgendeinen Weg gibt, wie ich less my computation time anders machen kann.
Irgendwelche Webseiten, Material zu verstehen, was und wie zu tun?
Wenn Sie mehrere Abfragen für dasselbe Array ausführen, können Sie eine Segmentstruktur 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) durchgeführt werden.
Beispiel für den Median im Bereich Segmentbaum:
Sie bauen den Segmentbaum von unten nach oben auf (Update von oben nach unten):
%Vor%Von Knoten abgedeckte Indizes:
%Vor%Eine Abfrage für den Median für die Bereichsindizes von 4-6 würde diesen Pfad der Werte durchlaufen:
%Vor%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.
%Vor%Es ist möglich, den Median ohne Sortieren in O (n) Zeit zu finden; Algorithmen, die dies tun, werden Auswahlalgorithmen genannt.
Um den Median eines Arrays mit weniger als 9 Elementen zu finden, halte ich einen Sortieralgorithmus wie Insertion sort für am effizientesten. Die Komplexität ist schlecht, aber für solch ein kleines Array ist wegen der k in der Komplexität von besseren Algorithmen wie Quicksort, Insertion sort sehr effizient. Machen Sie Ihren eigenen Benchmark, aber ich kann Ihnen sagen, dass Sie bessere Ergebnisse mit Insertion sort haben werden als mit shell sort oder quicksort.
Ich denke, der beste Weg ist, den Median des Median-Algorithmus zu verwenden, um das k-te größte Element eines Arrays zu zählen. Die allgemeine Idee des Algorithmus finden Sie hier: Median der Median in Java , auf wikipedia: Ссылка 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.
Tags und Links algorithm c math c++ data-structures