Es gibt eine Funktion F(), die alle n Zahlen sortieren kann, jetzt gibt es n^2 Zahlen müssen sortieren, wie oft anrufen F() Du brauchst wenigstens ? (Sie können nur F()) anrufen. Ich dachte mir eine Methode wie Bubble-Sort, etwa O (n^2) mal aufrufen. Gibt es einen besseren Weg?sort n^2 Zahlen nur mit der Funktion, die n Zahlen sortieren kann
Null. Sie können eine neue Funktion schreiben, die n^2-Nummern sortiert, und Sie müssen F() nicht aufrufen. Ist das Betrug? Ich denke nicht. Es hängt vollständig davon ab, was Sie zusätzlich tun dürfen, außer F().
Sie können n^2 Zahlen in n Gruppen von n Zahlen partitionieren und F() auf der jede Gruppe nennen, und dann auf n Listen n Zahlen eine Verschmelzung tun. Dies ist auch eine plausible Lösung, außer dass Sie es immer noch als Betrug bezeichnen.
Es kann spezifischere Lösungen geben, wenn Sie die Frage weiter einschränken möchten, aber Sie müssen diese Einschränkungen explizit buchstabieren.
Der erste Teil ist nicht konstruktiv, Die Frage nicht angegeben, Sie müssen 'F()' verwenden, aber es ist offensichtlich der Zweck der Frage. Die zweite ist eine Möglichkeit, es zu tun, und nicht zu betrügen, aber wie oft brauchen Sie? bei meiner Zählung wäre es "(n^2) -n" mal. –
Das hängt davon ab, wie Sie sie zusammenführen. Sie können 'F()' aufrufen (was suboptimal ist) und Sie können wählen, nicht (sagen wir mit einem Heap). Wenn Sie jedoch einen Heap verwenden möchten, können Sie dies zunächst tun, ohne 'F()' zu nennen. Deshalb denke ich, dass die Frage vage definiert ist. –
Einschränkungen: Sie können keine andere Operation ausführen, die die Position der Nummer ändert. – newSolar
Sie benötigen n (2n-1) Schritte (worst case). Hier ist eine intuitive Erklärung:
Angenommen, es gibt 4 sortierte Gruppen der Größe (n/2) jeder. Nennen wir sie A, B, C, D. Nehmen Sie auch an, dass jede dieser Gruppen sortiert ist, dass der anfängliche Eingabevektor DCBA ist und dass der endgültige sortierte Vektor ABCD sein sollte.
In jeder einzelnen Operation können wir die Reihenfolge von 2 Gruppen ändern (z. B. BA zu AB ändern).
DCBA Sortieranlage erfordert die folgenden Schritte:
DCBA -> CDAB (2 Schritte) -> CADB (1 Stufe) -> ACBD (2 Schritte) -> ABCD (Schritt 1)
Gesamtschritte: 6 = 4 * 3/2
Jetzt unterstützen, dass Sie FEDCBA sortieren müssen:
FEDCBA -> EFCDAB (3 Stufen) -> ECFADB (2 Stufen) -> CEAFBD (3 Schritte) -> CAEBFD (2 Schritte) -> ACBEDF (3 Schritte) -> ABCDEF (2 Schritte)
Gesamtschritte: 15 = 6 * 5/2
Und so weiter ....
Um x (x-1) müssen/sortieren x Blöcke der Größe (n/2), die jeweils Sie 2 Schritte (jeder Schritt sortiert n aufeinanderfolgende Elemente).
n² Elemente sind 2n * (n/2) Blöcke, Sie benötigen also (2n) (2n-1)/2 = n (2n-1) Schritte.
Edit:
Was passiert, wenn ein einzelner n-Sortierer (F) können beliebige Elemente sortiert werden sollen (nicht unbedingt in Folge)?
Dies stellt ein Problem auf Forschungsebene im Zusammenhang mit sorting networks. Siehe auch here.
Werfen Sie einen Blick auf diese recent paper by Shi, Yan, and Wagh:
In dieser Arbeit schlagen wir vor, einen n-Wege-Algorithmus Verschmelzung, die unter Verwendung von n-Sortierer als Grundbausteine, wo die oddevenMerge verallgemeinert n (≥ 2) ist Primzahl. Basierend auf diesem Zusammenführungsalgorithmus schlagen wir auch einen Sortieralgorithmus vor. Für N = n^p Eingangswerte werden p + ⌈n/2⌉ × p (p-1)/2 Stufen benötigt. Die Komplexität des Sortiernetzes wird anhand der Gesamtzahl der n-Sortierer ausgewertet. Der Ausdruck der geschlossenen Form für die Anzahl der Sortierer wird ebenfalls abgeleitet.
Ich stimme zu. Genau das, was ich dachte. –
Danke für deine Antwort, wenn das F() nur fortlaufende Nummern sortieren kann, ist deine Lösung völlig richtig. Aber wenn F() diskontinuierliche Zahlen sortieren kann, wie löst man? – newSolar
Was würden Sie tun, wenn Sie 'n + 1'-Nummern hätten? –
Folge @Alan Tam's Antwort/Bemerkung - darfst du noch etwas anderes benutzen? andere Funktion? Vergleiche? etwas DS? –
Teilen Sie die Nummern in drei Teile: die ersten n/2 Zahlen, die nächsten n/2 Zahlen, die letzte. Das Problem genau wie drei Zahlen vergleichen – newSolar