Eine Operation für eine Anwendung, die einen AVL-Baum verwendet, hat die Zeit O (log N). Es dauert ungefähr 50 Millisekunden, um auf einer Sammlung von 10.000 Elementen auszuführen. Wie lange würdest du erwarten, dass es dauern würde, um auf einer Sammlung von 100.000 Elementen zu laufen?Wie finden Sie Zeit in Avl Trees?
Sie können einfach nicht die Zeit erraten, die es dauern würde, um es auf einer größeren Sammlung laufen zu lassen, weil Sie alle konstanten Berechnungskosten Ihrer Anwendung (d. H. Laden, Vorverarbeitung usw.) berücksichtigen müssen.
Sie können jedoch eine obere Grenze finden: log (10000) = 4, log (100000) = 5, so dass Sie erwarten könnten, dass es in weniger als 5/4 * 50 = 62,5 ms läuft, sofern Sie bereits erreicht haben das asymptotische Verhalten.
Wie auch immer, O (log N) ist eine sehr effiziente Komplexität, Ihr Algorithmus sollte sehr gut auf große Instanzen skalieren.
N Elemente zu behandeln, müssen Sie ungefähre Zeit
T ~ C * N * log (N)
für 10000:
50 ms = C * 10^4 * log(10^4) = C * 4 * 10^4 * log(10)
C = 50ms/(4 * 10^4 * log(10))
für 100000:
T ~ 50ms/(4 * 10^4 * log(10)) * 5 * 10^5 * log(10)
T ~ 50ms * 5 * 10/4 = 625 ms
So würden Sie Zeit etwa 625 ms
erwarten
Ich muss hinzufügen, dass oth Er scheint eine Komplexität von O (N log N) anstelle von O (log N) verstanden zu haben, was die übliche Komplexität für eine Abfrage in einem sortierten Baum ist (z. B. eine Karte in C++). Außerdem ändert die Basis des Logarithmus nichts, da sie in der großen O-Notation berücksichtigt wird. (log n = ln n/ln 10) – pvallet