Algorithmische Komplexität
Gibt an, wie viel elementare Schritte ein Algorithmus benötigt, um eine vorgegebene Aufgabe zu bewältigen.
Algorithmus
Eine endliche, exakt beschriebene Handlungsvorschrift (Standardbeispiel: Kochrezept, Euklid'scher Algorithmus)
Baum (im informatischen Sprachgebrauch)
Eine azyklische zusammenhängende graphische Struktur, die von einem eindeutig bestimmten Element (Wurzel) ausgeht. Aus den Knoten (also insbesondere auch aus der Wurzel) gehen Kanten hervor, an denen weitere Knoten angeordnet sind. Gehen aus diesen Knoten keine weiteren Kanten hervor, spricht man von Endknoten oder Blättern. Hängt an solch einem inneren Knoten noch eine weitere Struktur (hat er also Nachfolger-Knoten), bildet dieser innere Knoten gemeinsam mit den ihm zugeordneten Substrukturen einen Teilbaum.
Bäume als Graphen werden in der Regel von der Wurzel ausgehend nach unten gezeichnet.
Baum, binärer
Spezialfall eines Baumes, bei dem jeder Knoten maximal zwei Nachfolger hat. Sie spielen in der Informatik als Such- und Entscheidungsbäume eine besondere Rolle.
Bubble-Sort
Sortierverfahren, bei dem durch wiederholten Vergleich und wenn nötig durch Positionstausch der Nachbarelemente sortiert wird.
Graph
Mathematische Struktur, die aus Knoten (Elementen) und Kanten (Verbindungen) besteht. Je nach Aufbau der Verbindungselemente können Graphen zyklisch (Netze) oder azyklisch (Bäume, Sequenzen) sein.
Insertion-Sort
Sortierverfahren, bei dem das jeweils erste Element des noch unsortierten Teilbereichs an die aktuell richtige Position im bereits sortierten Teilbereich gebracht wird.
Mergesort
Effizientes Sortierverfahren, das durch Halbierung und anschließendes vergleichendes Mischen von Teilfolgen Sortiertheit erzielt. Eignet sich grundsätzlich auch für externes Sortieren.
O(n), O(n · ld(n)), O(n2)
Komplexitätsangabe von Algorithmen in Abhängigkeit vom Umfang n der zu bewältigenden Aufgabe. Ein Algorithmus hat lineare (oder O(n)) Komplexität, wenn die Bearbeitungsdauer im Durchschnitt proportional zur Anzahl der zu bearbeitenden Elemente ist. Er hat quadratische (O(n2)) Komplexität, wenn die Bearbeitungsdauer mit dem Quadrat der Anzahl der zu bearbeitenden
Elemente steigt. Bei logarithmischer Komplexität steigt sie nur mit dem Logarithmus der Zahl der Elemente.
Konstante Glieder oder Faktoren spielen dabei eine vernachlässigbare Rolle. Wenn eine Analyse etwa zeigt, dass 3 n2 + 270 n + 1000 Schritte nötig sind, spricht man dennoch von einem O(n2), also quadratischen Verfahren, weil bei hinreichend großem n das Faktum, dass dieses quadratisch in die Formel eingeht, dominiert.
Für Sortierverfahren sind O(n · ld(n)) Verfahren von besonderer Bedeutung, weil man zeigen kann, dass der allgemeine Fall von in-situ Sortierung ohne Parallelität im Schnitt mindestens n x Logarithmus-Dualis von n Schritte benötigt.
Quicksort
Effizientes Sortierverfahren, das eine Folge anhand eines Vergleichselements in eine Teilfolge mit Elementen, die kleiner(gleich) dem Vergleichselement und eine Teilfolge mit Elementen, die größer(gleich) dem Vergleichselement sind, aufspaltet. Durch rekursive Wiederholung entsteht Sortiertheit.
Selection-Sort
Sortierverfahren, bei dem das jeweils minimale Element des noch unsortierten Teilbereichs an das Ende des bereits sortierten Teilbereichs gebracht wird.
Gibt an, wie viel elementare Schritte ein Algorithmus benötigt, um eine vorgegebene Aufgabe zu bewältigen.
Algorithmus
Eine endliche, exakt beschriebene Handlungsvorschrift (Standardbeispiel: Kochrezept, Euklid'scher Algorithmus)
Baum (im informatischen Sprachgebrauch)
Eine azyklische zusammenhängende graphische Struktur, die von einem eindeutig bestimmten Element (Wurzel) ausgeht. Aus den Knoten (also insbesondere auch aus der Wurzel) gehen Kanten hervor, an denen weitere Knoten angeordnet sind. Gehen aus diesen Knoten keine weiteren Kanten hervor, spricht man von Endknoten oder Blättern. Hängt an solch einem inneren Knoten noch eine weitere Struktur (hat er also Nachfolger-Knoten), bildet dieser innere Knoten gemeinsam mit den ihm zugeordneten Substrukturen einen Teilbaum.
Bäume als Graphen werden in der Regel von der Wurzel ausgehend nach unten gezeichnet.
Baum, binärer
Spezialfall eines Baumes, bei dem jeder Knoten maximal zwei Nachfolger hat. Sie spielen in der Informatik als Such- und Entscheidungsbäume eine besondere Rolle.
Bubble-Sort
Sortierverfahren, bei dem durch wiederholten Vergleich und wenn nötig durch Positionstausch der Nachbarelemente sortiert wird.
Graph
Mathematische Struktur, die aus Knoten (Elementen) und Kanten (Verbindungen) besteht. Je nach Aufbau der Verbindungselemente können Graphen zyklisch (Netze) oder azyklisch (Bäume, Sequenzen) sein.
Insertion-Sort
Sortierverfahren, bei dem das jeweils erste Element des noch unsortierten Teilbereichs an die aktuell richtige Position im bereits sortierten Teilbereich gebracht wird.
Mergesort
Effizientes Sortierverfahren, das durch Halbierung und anschließendes vergleichendes Mischen von Teilfolgen Sortiertheit erzielt. Eignet sich grundsätzlich auch für externes Sortieren.
O(n), O(n · ld(n)), O(n2)
Komplexitätsangabe von Algorithmen in Abhängigkeit vom Umfang n der zu bewältigenden Aufgabe. Ein Algorithmus hat lineare (oder O(n)) Komplexität, wenn die Bearbeitungsdauer im Durchschnitt proportional zur Anzahl der zu bearbeitenden Elemente ist. Er hat quadratische (O(n2)) Komplexität, wenn die Bearbeitungsdauer mit dem Quadrat der Anzahl der zu bearbeitenden
Elemente steigt. Bei logarithmischer Komplexität steigt sie nur mit dem Logarithmus der Zahl der Elemente.
Konstante Glieder oder Faktoren spielen dabei eine vernachlässigbare Rolle. Wenn eine Analyse etwa zeigt, dass 3 n2 + 270 n + 1000 Schritte nötig sind, spricht man dennoch von einem O(n2), also quadratischen Verfahren, weil bei hinreichend großem n das Faktum, dass dieses quadratisch in die Formel eingeht, dominiert.
Für Sortierverfahren sind O(n · ld(n)) Verfahren von besonderer Bedeutung, weil man zeigen kann, dass der allgemeine Fall von in-situ Sortierung ohne Parallelität im Schnitt mindestens n x Logarithmus-Dualis von n Schritte benötigt.
Quicksort
Effizientes Sortierverfahren, das eine Folge anhand eines Vergleichselements in eine Teilfolge mit Elementen, die kleiner(gleich) dem Vergleichselement und eine Teilfolge mit Elementen, die größer(gleich) dem Vergleichselement sind, aufspaltet. Durch rekursive Wiederholung entsteht Sortiertheit.
Selection-Sort
Sortierverfahren, bei dem das jeweils minimale Element des noch unsortierten Teilbereichs an das Ende des bereits sortierten Teilbereichs gebracht wird.