Dies ist eine Hausaufgabenfrage, daher möchte ich möglichst vollständige Antworten vermeiden und wenn möglich viel mehr Tipps geben.
Wenn ein Array von zufälligen ganzen Zahlen A [1 ... x] gegeben wird, sollte das Programm die ersten y-Array-Elemente in aufsteigender Reihenfolge zurückgeben, wobei 1 & lt; = y & lt; = sqrt (x). Im Grunde sollte das Programm bei gegebenem Array [5,9,2,8] und y = 2 das Ergebnis [2,5] zurückgeben.
Die Antwort "Sortiere zuerst, gib zuerst y-Elemente zurück" ist aus dem Fenster, da das Beste, was wir tun können, n * logn time mit merge oder quicksort ist. Die Antwort muss also die Tatsache nutzen, dass wir nur die meisten sqrt (x) -Einträge zurückgeben, und die einzige andere Antwort, die ich bisher gemacht habe, ist eine For-Loop-Suche nach dem minimalen Element im Array, wobei das Minimum aus entfernt wird Das Array, das in einem neuen Array gespeichert wird, sagen wir B, und wiederholen den Prozess auf der nun kleineren modifizierten Version von A der Länge x-1, was uns die Laufzeit ähnlich macht:
%Vor%Dies zählt die Anzahl der For-Loop-Iterationen der Min-Suche und gibt uns im schlimmsten Fall höchstens y oder sqrt (x) Iterationen, und es gibt höchstens x Elemente im Array. Also haben wir sqrt (x) * x, was besser ist als O (n * logn), aber immer noch nicht ganz O (n): /.
Tipp: Angenommen, Sie hätten einen O (n) -Zeitalgorithmus, um das y th -Element auszuwählen ...
Tatsächlich wächst sqrt (x) schneller als log (x), also ist O (x * sqrt (x)) schlechter als O (n * log (x)). Sie haben also (noch) nicht besser gemacht, als die ganze Liste zu sortieren.
Es gibt mehrere Möglichkeiten, dieses Problem zu lösen. Für einen von ihnen schauen Sie sich Ссылка an und betrachten Sie alle gängigen Sortieralgorithmen. Welcher Algorithmus kann Ihnen die ersten Elemente am effizientesten vermitteln?
Verwenden Sie für y die Schnellsortiervorschläge, wählen Sie eine Zufallszahl und partitionieren Sie sie in zwei Teile.
Part1 (kleiner) und part2 (größer).
Wenn Länge von Part1 & lt; y, dann mach die Partition in Part2 mit y '= y - len (Part1)
Wenn Länge von Part1 & gt; y, dann mache die Partition in Part1 mit y '= y
Wenn die Länge von Part1 == y ist, dann sortiere Part1.
Für die Partitionierung sollte der Durchschnitt fast in O (n) liegen (ich kann es jetzt nicht genehmigen, aber es ist sehr schnell) (Ich werde versuchen, etwas Material für diesen Teil zu finden).
Nach y sortieren benötigt ylog (y) & lt; sqrt (x) log (sqrt (x)) - & gt; 1/2 * sqrt (x) * log (x) & lt; 1/2 * sqrt (x) * sqrt (x) = & gt; 1/2 x.
Sie wollen nur einen Hinweis, oder?
Lesen Sie den Kommentar von random_hacker sehr sorgfältig für den Fall, dass Sie den großen Hinweis verpasst haben, den er gibt. Es gibt einen Algorithmus zum Sortieren eines Arrays, bei dem eine kleine, winzige Änderung Ihren Algorithmus erzeugt.
Wenn y nicht auf sqrt (x) beschränkt ist, erhalten Sie im Allgemeinen einen Algorithmus, der in O (x + y * log x) arbeitet, also O (x), wenn y = O (x / log x) , was natürlich der Fall ist, wenn y & lt; = sqrt (x).