In Groß-O-notation für Baum-Strukturen: Warum tun einige Quellen beziehen sich auf O(logN) und einige auf-O(h)?

In der Erforschung der Komplexität für jeden Algorithmus durchsucht einen binären Suchbaum, ich sehe zwei verschiedene Möglichkeiten, etwas auszudrücken:

Version #1: Die traversal Algorithmus im worst-case vergleicht einmal pro Höhe des Baumes; daher Komplexität ist O(h).

Version #2: Der traversal Algorithmus im worst-case vergleicht einmal pro Höhe des Baumes; daher Komplexität ist O(logN).

Scheint es mir, dass die gleiche Logik am Werk ist, noch verschiedenen Autoren entweder logN oder h. Kann mir jemand erklären, warum dies der Fall ist?

InformationsquelleAutor Stephen Gross | 2012-02-03

8

Wenn Ihr binären Baums ist ausgewogen, so dass jeder Knoten hat genau zwei Kind-Knoten, dann die Anzahl der Knoten im Baum genau N = 2^h − 1, also die Höhe ist der Logarithmus der Anzahl der Elemente (und so ähnlich für eine vollständige n-ary tree).

Einer beliebigen, lockere Baum kann völlig unterschiedlich Aussehen, obwohl, zum Beispiel, könnte es nur einen Knoten auf jeder Ebene, so N = h in diesem Fall. Also die Höhe ist die Allgemeine Maßnahme, da es sich um ist-Vergleiche, aber unter der zusätzlichen Annahme von Gleichgewicht Sie Ausdrücken kann die Höhe als der Logarithmus der Anzahl der Elemente.
- Eine wichtige, aber nitpicky Punkt - nicht alle ausgewogene Bäume jeder Knoten mit zwei Kindern, und wenn jeder interne Knoten zwei Kinder haben garantiert nicht die balance. Viele ausgeglichene Bäume (AVL-Bäume, Rot/Schwarz-Bäume, AA-Bäume, RAVL Bäume, etc.) gehorchen nicht diesem Zustand, aber immer noch O(log n) - Suchvorgänge, wo das Protokoll nicht base-2.
- das ist, weil Sie nicht "ausgewogen, so dass jeder Knoten hat genau zwei Kind-Knoten". Ein AVL-Baum ist maximal symmetrisch für seine Größe, die invariant ist, daß keine Knoten den Teilbaum, dessen Höhe unterscheidet sich um mehr als eine. IIRC für Rot-Schwarz-Bäume die Einschränkung, daß keine Knoten den Teilbaum, dessen Höhe variiert um mehr als einen Faktor 2 -- Sie sind "weniger ausgewogen" als AVL-Bäume, aber trotzdem immer noch "ausgewogen" genug für h zu O(log n). Die log im O(log n) noch base 2 oder eine andere base, da die Wahl der Basis macht nur eine Konstante-Faktor-Differenz.
- Ich auch weggelassen für die Einfachheit, dass die Letzte Zeile der Baum muss nicht voll sein, natürlich, und du hast Recht, dass zwischen den Zeilen auch nicht haben, um eine bestimmte Größe, sondern die Anzahl der Elemente begrenzt, die oben und unten. Letztlich, was zählt, ist, dass h = O(log N) (und beliebiger stelligkeit ist zusammengefasst in der Konstanten).
InformationsquelleAutor Kerrek SB
15

Den richtigen Wert für das worst-case-Zeit zu suchen ist-Baum ist O(h), wobei h die Höhe des Baumes. Wenn Sie mit einer ausgewogenen Suche nach Baum (eine, wo die Höhe des Baumes ist O(log n)), dann die lookup-Zeit worst-case O(log n). Das heißt, nicht alle Bäume sind balanciert. Für Beispiel, hier ist ein tree mit Höhe n - 1:
```
1
 \
  2
   \
    3
     \
     ...
       \
        n
```
Hier h = O(n), also den lookup ist O(n). Es ist richtig zu sagen, dass die lookup-Zeit ist auch O(h), aber h ≠ O(log n) in diesem Fall, und es wäre falsch zu behaupten, dass die lookup-Zeit war O(log n).

Kurz, O(h) ist die richtige gebunden. O(log n) ist die richtige Bindung für eine ausgeglichene Suchbaum, wenn die Höhe ist höchstens O(log n), aber nicht alle haben die Bäume lookup-Zeit von O(log n), da Sie möglicherweise unausgewogen.

Hoffe, das hilft!

InformationsquelleAutor templatetypedef
2

O(h) beziehen würde, um ein binärer Baum ist sortiert, aber nicht ausgewogen

O(logn) finden würde, an einen Baum, die sortiert und ausgewogen

InformationsquelleAutor hrezs
1

Es ist eine Art von zwei Arten, dasselbe zu sagen, weil Ihre Durchschnittliche ausgeglichenen binären Baum der Höhe h ' wird um 2^h-Knoten.

Je nach Kontext, entweder die Höhe oder die #Knoten kann mehr relevant, und so ist das, was Sie sehen, auf die verwiesen wird.

InformationsquelleAutor dkamins
0

weil die (h)acht auf eine ausgewogene Struktur variiert, da das Protokoll von der (N)nzahl der Elemente
- Nicht immer; unbalancierte Bäume haben können, h = Theta(n).
- Ich habe irgendwie angenommen, er war eine Anspielung auf die symmetrische und die Frage entstand, weil er sah verschiedene Schreibweisen für den gleichen Fall. logN ist eindeutig der symmetrische Fall. Editiert für die Klarheit sowieso.
- Tatsächlich in der re-Lektüre die Frage, beide erwähnen "worst case", aber im schlimmsten Fall h = N und also eine der beiden Aussagen, die er zitiert, ist wahrscheinlich falsch. Wenn h == N der Aussagen führt zu h = = - log(h) ist nicht möglich
InformationsquelleAutor Gus

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.