Untergrenze für die zeitliche Komplexität der gefundenen k-Paare finden

Question

Wir haben n Schrauben und n Muttern verschiedener Größen, wobei jede Schraube genau mit einer Mutter übereinstimmt. Unser Ziel ist es, für jede Schraube die passende Mutter zu finden. Die Schrauben und Muttern sind zu ähnlich, um direkt zu vergleichen; Wir können jedoch prüfen, ob eine Mutter zu groß, zu klein oder genauso groß wie eine Schraube ist.

Beweisen Sie, dass im schlimmsten Fall Ω (n + k log n) Muttern-Schrauben-Vergleiche erforderlich sind, um k passende Paare zu finden.

Ich bin gründlich ratlos, wie dies zu tun ist, ich denke, ein 3-stufiger Entscheidungsbaum mit dafür würde n^k Knoten benötigen, also klog (n) für die Höhe des Baumes geben, aber ich kann ' t Finde heraus, woher das + n kommt.

Answer 1

Hier ist eine sehr lockere Antwort, die die Grundlage eines geeigneten Nachweis bilden könnte:

Angenommen, Sie mich fragen (euer Widersacher) jedes Mal, wenn Sie wollen eine neue Mutter oder einen neuen Bolzen testen und ich gib dir eine neue Nuss oder einen neuen Bolzen. Bevor Sie beginnen, sortiere ich die Schrauben und Muttern in passende Paare, dann unterteilen Sie die Paare in zwei Haufen, jede der Größe n/2. Für die ersten n/2 Schritte gebe ich dir eine Nuss vom ersten Haufen oder einen Bolzen vom zweiten Haufen, je nachdem, was du verlangst. So kann ich Sie immer davon abhalten, Treffer zu finden, bis Sie mindestens n/2 übereinstimmende Versuche gemacht haben, weil, bis ich von einem der Haufen auslaufe, Sie nie eine Nuss und einen Bolzen bekommen werden, die übereinstimmen.

Ihr Leben wird nicht schwieriger, wenn ich die Schrauben in der Reihenfolge der Größe beschrifte, weil Sie diese Informationen immer ignorieren können. Wenn Sie nun k Übereinstimmungen in der Zeit kleiner als k log n für alle möglichen k und n> = k finden, dann können Sie das Problem der Sortierung von n Zahlen nur durch Vergleiche lösen, wobei bekannt ist, dass die Zahlen die Menge {1 sind , 2,3 ... n}. In der Tat, auch wenn Sie eine magische Methode haben, die nur für z. k < = 3 und alle n, Sie können immer noch diese Vergleichssortierung durchführen, indem Sie wiederholt 3 Übereinstimmungen zwischen der Menge der verbleibenden (unbeschrifteten) Muttern und der Menge der (markierten) Schrauben finden. Wenn Sie also Übereinstimmungen mit weniger als k log n Vergleich finden, können Sie Zahlen, die bekanntermaßen {1,2 ... n} sind, mit weniger als n log n Vergleichen sortieren - aber die übliche informationstheoretische Untergrenze für die Sortierung von Zahlen immer noch hält hier. Sie brauchen also mindestens k log n Vergleiche.

Also jetzt haben wir eine untere Grenze von max (n/2, k log n). Wir interessieren uns nicht für Faktoren, also haben wir max (n, k log n). Aber (a + b)/2 < = max (a, b) < = a + b für a, b> = 0 also wieder vernachlässigen Faktoren können wir dies in n + k log n verwandeln.