EMZETT.Glossar
1620 Begriffe aus IT, Netzwerk, Sicherheit und Programmierung: erst kurz erklärt, dann ausführlicher. Suche nach einem Wort oder wähle einen Buchstaben.
3 Treffer
Binäre Suche Die binäre Suche findet ein Element in einer sortierten Liste, indem sie den Suchbereich immer wieder halbiert – statt alle Elemente einzeln zu prüfen.
Sie vergleicht den gesuchten Wert mit dem mittleren Element: Ist er kleiner, geht es links weiter, ist er größer, rechts. Dadurch braucht sie bei n Elementen nur etwa log₂(n) Schritte – bei einer Million Elementen höchstens 20 (Laufzeit O(log n), siehe Big-O-Notation). Voraussetzung ist eine sortierte Datenmenge mit Indexzugriff.
Verwandt: Algorithms (Algorithmen) · Index · Baum (Datenstruktur) · Big-O-Notation · Mergesort · Sorting (Sortieren)
Ganzer Artikel im Wiki →Baum (Datenstruktur) Ein Baum ist eine hierarchische Datenstruktur aus Knoten, die über Kanten verbunden sind: Ein Wurzelknoten hat Kinder, diese wieder Kinder – ohne Kreise.
Bäume bilden Hierarchien ab: Dateisysteme, HTML-Dokumente (DOM), Organigramme und Entscheidungen. Der binäre Suchbaum speichert Werte so, dass links nur kleinere und rechts nur größere Werte hängen – dadurch lässt sich in O(log n) suchen, solange er ausgeglichen ist.
Verwandt: Graph (Datenstruktur) · Queue (Warteschlange) · Stack (Stapel) · Baum-Topologie · Big-O-Notation · Binäre Suche
Ganzer Artikel im Wiki →Teile und herrsche (Divide and Conquer) Teile und herrsche zerlegt ein Problem in kleinere gleichartige Teilprobleme, löst sie (oft rekursiv) und setzt die Teillösungen zusammen.
Drei Schritte: teilen, die Teile lösen, zusammenführen. Klassische Beispiele sind Mergesort, Quicksort und die Binäre Suche. Oft ergibt sich daraus eine Laufzeit von O(n log n) statt O(n²).
Verwandt: Big-O-Notation · Binäre Suche · Dynamische Programmierung · Mergesort · Quicksort · Recursion (Rekursion)
Ganzer Artikel im Wiki →