Ich habe folgende Hausaufgabe (bitte beachten Sie, dass ich nicht nach genauen Antworten suche, sondern nur nach einfachen Vorschlägen, um weiterzukommen).
S ist eine Datenstruktur, die die Funktionen Insert(x,S), Delete(x, S) und Find_Smallest_Item(S) in Zeit <= T(n) unterstützt. Beweisen Sie eine untere Schranke für T(n) wie z.B. (logn).
Hier sind meine bisherigen Gedanken:
Ich denke, ich muss eine Reduktion finden, mit der ich dieses Problem auf ein einfacheres reduzieren und beweisen kann, dass es nicht kleiner als logn sein kann. Ich habe viele Tutorials über untere Schranken gelesen und die meisten von ihnen haben ein Problem auf die Sortierung reduziert, dann haben sie die Sortierung als Blackbox verwendet und bewiesen, dass der Algorithmus nicht kleiner als nlogn sein kann.
Aber hier haben wir es mit logn zu tun und ich kenne keinen solchen Algorithmus, auf den man reduzieren könnte. Vielleicht muss es etwas mit der Tiefe einer Baumstruktur, logn, zu tun haben. Aber ich konnte nicht herausfinden, wo ich anfangen sollte.
Können Sie mir einige Tipps geben?
Editar : Eigentlich ist mir etwas in den Sinn gekommen, aber ich weiß nicht, ob ich mit so einem Trick eine untere Schranke beweisen soll. Ich nehme also an, dass ich Einfüge-, Lösch- und find_smallest-Operationen habe, von denen jede eine logn-Zeitkomplexität hat.
Um beispielsweise eine sortierte Liste zu erstellen, kann ich die Funktionen delete und find_smallest verwenden, z. B. kann ich find_smallest zum ersten Mal ausführen, und nachdem ich das kleinste Element in der Liste gefunden habe, werde ich das Element löschen. Ich führe es noch einmal aus und finde so das zweitkleinste Element usw.
Daher kann ich die Sortierung mit den Funktionen deletion und find_smallest durchführen. Wenn ich das also n-mal mache, dauert jedes Mal logn (für das Löschen) + logn (für das Finden des Kleinsten), so dass das Sortieren insgesamt nlogn dauert.
Ich weiß allerdings nicht, wie ich das für die Einfügung optimieren kann.
Bearbeiten 2: Um die Einfügung für den Beweis zu verwenden: nachdem ich das i-te kleinste Element in der Liste gefunden habe, was ist, wenn ich es an der i-ten Stelle einfüge? z.B. nachdem ich das drittkleinste Element mit der obigen Prozedur gefunden habe, kann ich es am dritten Index der Datenstruktur einfügen. Somit erhalte ich am Ende eine sortierte Datenstruktur.
