Ist O (logn) immer ein Baum?

Question

Wir sehen immer Operationen auf einem (binären Such-) Baum hat o (logn) schlechteste Falllaufzeit, da die Baumhöhe logn ist. Ich frage mich, ob uns gesagt wird, dass ein Algorithmus die Laufzeit in Abhängigkeit von logn, z. M + NLOGN hat, schließen, dass er einen (erweiterten) Baum beinhalten muss?

Bearbeiten: Dank Ihrer Kommentare erkennen ich jetzt, dass die Divide-Berg- und binäre Baum visuell/konzeptionell so ähnlich sind. Ich hatte nie eine Verbindung zwischen den beiden hergestellt. Aber ich denke an einen Fall, in dem O (logn) kein Divide-Conquer-Algo ist, an dem ein Baum beteiligt ist, der keine Eigenschaft eines BST/AVL/rot-schwarzen Baums hat.

Das ist die disjunkte Datenstruktur mit Find/Union Operations, deren Laufzeit O (N + MLOGN) ist, wobei n die Anzahl der Elemente und M die Anzahl der Fundoperationen ist.

Bitte lassen Sie mich wissen, ob ich STH fehle, aber ich kann nicht sehen, wie sich hier einteilen. Ich sehe nur in diesem (disjunkten) Fall, dass es einen Baum ohne BST -Eigenschaft und eine Laufzeit für logn hat. Meine Frage geht also darüber, warum/warum nicht ich aus diesem Fall eine Verallgemeinerung vornehmen kann.

Answer 1

Was Sie haben, ist genau rückwärts. O(lg N) Im Allgemeinen bedeutet eine Art Kluft und Erobereralgorithmus, und eine gemeinsame Möglichkeit zur Umsetzung von Klassifien und Eroberung ist ein binärer Baum. Während binäre Bäume eine wesentliche Untergruppe aller Divide-and-Conquer-Algorithmen sind, sind die Teilmengen sowieso eine Untergruppe.

In einigen Fällen können Sie andere Divide- und Erobereralgorithmen ziemlich direkt in binäre Bäume verwandeln (z. B. Kommentare zu einer anderen Antwort haben bereits versucht, eine binäre Suche ähnlich zu beanspruchen). Nur für ein weiteres offensichtliches Beispiel jedoch ein Multiway-Baum (z. nicht ein binärer Baum.

Wenn Sie noch dringend genug wollen, können Sie den Punkt dehnen, dass ein Multiway -Baum als eine Art verzerrte Version eines binären Baums dargestellt werden kann. Wenn Sie möchten, können Sie wahrscheinlich alle Ausnahmen bis zu sagen, dass alle von ihnen (zumindest so etwas wie) binäre Bäume sind. Zumindest für mich ist nur für mich nur "binärer Baum" gleichbedeutend mit "Divide and Eroberung". Mit anderen Worten, Sie erreichen nur das Vokabular und löschen einen Begriff, der sowohl eindeutig als auch nützlich ist.

Answer 2

Nein, Sie können auch binäre Binäranlagen suchen (z. B.). Aber nimm mein Wort nicht dafür http://en.wikipedia.org/wiki/binary_search_algorithmus

Answer 3

Als Gegenbeispiel:

given array 'a' with length 'n'
y = 0
for x = 0 to log(length(a))
    y = y + 1
return y

Die Laufzeit ist o (log (n)), aber hier kein Baum!

Answer 4

Antwort ist nein. Binäre Suche nach einem sortierten Array ist O(log(n)).

Answer 5

Algorithmen, die logarithmische Zeit nehmen, sind häufig gefunden in Operationen auf binären Bäumen.

Beispiele für O (logn):

• Finden eines Elements in einem sortierten Array mit einer binären Suche oder einem ausgewogenen Suchbaum.

• Schauen Sie sich einen Wert in einem sortierten Eingangsarray nach Halbzeit nach.

Answer 6

Da ist O (log (n)) nur eine Obergrenze auch alle o (1) -Algorithmen wie function (a, b) return a+b; den Zustand erfüllen.

Aber ich muss zustimmen, dass alle Theta (log (n)) -Algorithmen irgendwie wie Baumalgorithmen aussehen oder zumindest an einen Baum abstrahiert werden können.

Answer 7

Kurze Antwort:

Nur weil ein Algorithmus als Teil seiner Analyse log (n) hat, bedeutet dies nicht, dass ein Baum beteiligt ist. Zum Beispiel ist das Folgende ein sehr einfacher Algorithmus, der ist O(log(n)

for(int i = 1; i < n; i = i * 2)
  print "hello";

Wie Sie sehen können, war kein Baum beteiligt. John, bietet auch ein gutes Beispiel dafür, wie binäre Suche auf einem sortierten Array durchgeführt werden kann. Beide nehmen o (log (n)) Zeit und es gibt andere Code -Beispiele, die erstellt oder verwiesen werden könnten. Machen Sie also keine Annahmen, die auf der asymptotischen Zeitkomplexität beruhen, und schauen Sie sich den Code mit Sicherheit an.

Mehr auf Bäumen:

Nur weil ein Algorithmus "Bäume" beinhaltet O(logn) entweder. Sie müssen den Baumtyp kennen und wie sich die Operation auf den Baum auswirkt.

Einige Beispiele:

• Beispiel 1)

Das Einsetzen oder Durchsuchen des folgenden unausgeglichenen Baumes wäre O(n).

• Beispiel 2)

Einfügen oder Durchsuchen der folgenden ausgewogenen Bäume würden beide durch O(log(n)).

Ausgeglichener binärer Baum:

Ausgeglichener Baum von Grad 3:

zusätzliche Kommentare

Wenn die Bäume, die Sie verwenden, keine Möglichkeit haben, "Balance" zu haben, als es eine gute Chance gibt, dass Ihre Operationen sein werden O(n) Zeit nicht O(logn). Wenn Sie Bäume verwenden, die sich selbst ausbalancieren, nehmen Sie sich normalerweise mehr Zeit in Einklang, da das Ausgleich der Bäume normalerweise während der Einsatzphase auftritt.