Adjazenzlisten und durchschnittliche Zeitkomplexität für die binäre Suche (2 separate Fragen)

Question

Ist die durchschnittliche Zeitkomplexität für eine erfolgreiche binäre Suche in einem sortierten Array und in einem binären Suchbaum gleich, O (log (n))?

Auch sind die Worst-Case-Zeitkomplexität für beide gleich, O (n)?

---

Wenn eine Adjazenzliste für eine Grafik zu zeichnen, wird die Reihenfolge dieser Angelegenheit? Zum Beispiel wäre es falsch, dies zu ändern:

Zu diesem (Hinweis in der ersten Reihe, wie die 2 und 3 sind eingeschaltet):

Answer 1

Das Schlimmste und mittlere zum Suchen in einem sortierten Array ist O (Log n). Und das ist, weil, wenn das Array sortiert ist, Sie höchstens O (Log n) Sprünge machen, um zu schließen, dass das Element nicht existiert. In einem BST sind der schlechteste und der Durchschnitt O (n) bzw. O (Log n), wobei der schlimmste Fall auftritt, wenn der Baum vollständig verzerrt ist und sich somit wie eine verkettete Liste verhält.

---

Ihre Bestellung einige Ausführungs Rolle in können Sie durchführen können (wie DFS anderen Pfad zu einem anderen Knoten zurückkehrt), aber beide Liste adjacency Darstellungen sind absolut gültig.