Überprüfung der Komplexität der Splay-Baum Betrieb in Java

Question

I spreizen Baum implementiert haben (Einfügen, Suchen, Löschen-Betrieb) in Java. Jetzt möchte ich überprüfen, ob die Komplexität des Algorithmus O (logn) ist oder nicht. Gibt es eine Möglichkeit, dies zu überprüfen, indem Sie die Eingabewerte (Anzahl der Knoten) variieren und die Laufzeit in Sekunden überprüfen? Sagen wir, indem wir Eingabewerte wie 1000, 100000 setzen und die Laufzeit überprüfen oder gibt es andere Wege?

Answer 1

Streng genommen können Sie die zeitliche Komplexität des Algorithmus nicht finden, indem Sie ihn für einige Werte von n ausführen. Angenommen, Sie haben es für die Werte n_1, n_2, ..., n_k ausgeführt. Wenn der Algorithmus n^2 Operationen für alle n <= max(n_1, ..., n_k) und genau 10^100 Operationen für einen größeren Wert von n macht, hat er eine konstante Zeitkomplexität, obwohl er von den Punkten, die Sie haben, wie eine quadratische aussehen würde.

Sie können jedoch die Anzahl der Operationen beurteilen sie auf einen Eingang einer Größe in Anspruch nimmt n (ich würde es nicht einmal nennen Zeitkomplexität hier, da diese eine strenge formale Definition hat), indem Sie auf einige Werte laufen von n und bei Verhältnissen T(n1)/T(n2) und n1/n2 suchen. Aber selbst im Falle eines "echten" Algorithmus (in dem Sinne, dass es sich nicht um einen pathologischen Fall handelt, der im ersten Absatz beschrieben wird), sollten Sie vorsichtig mit der "Struktur" der Eingabe umgehen (zum Beispiel einen schnellen Sortieralgorithmus, der den Das erste Element als Pivot wird im Durchschnitt in O(n log n) für eine zufällige Eingabe ausgeführt, so dass es wie ein O(n log n) aussehen würde, wenn Sie zufällige Arrays unterschiedlicher Größe generieren würden, jedoch unter O(n^2) für ein umgekehrt sortiertes Array.

Um es zusammenzufassen, wenn Sie herausfinden müssen, ob es aus praktischer Sicht schnell genug ist und Sie eine Idee haben, wie eine typische Eingabe für Ihren Algorithmus aussieht, können Sie versuchen, Eingaben unterschiedlicher Größe zu generieren wie die Ausführungszeit wächst.

Wenn Sie jedoch eine mathematische Grenze für die Laufzeit benötigen, müssen Sie einige Eigenschaften und Grenzen Ihres Algorithmus mathematisch nachweisen.

In Ihrem Fall würde ich sagen, dass das Testen auf zufällige Eingaben eine vernünftige Idee sein kann (weil es einen mathematischen Beweis gibt, dass die Zeitkomplexität eines Vorgangs O(log n) für einen Splay-Baum ist), also müssen Sie das nur überprüfen Der von Ihnen implementierte Baum ist in der Tat ein korrekter Splay-Tree. Eine Anmerkung: Ich würde empfehlen, verschiedene Muster von Abfragen (wie das Einfügen von Elementen in sortierter/umgekehrter Reihenfolge usw.) zu versuchen, da sogar unausgeglichene Bäume ziemlich schnell arbeiten können, solange die Eingabe "zufällig" ist.