Nennen sie 3 Eigenschaften eines Algorithmus und erklären sie diese
Ein Algorithmus hat typischerweise folgende drei Eigenschaften:
1. **Eindeutigkeit (Determinismus)**: Jeder Schritt des Algorithmus muss eindeutig sein und eine klare Anweisung liefern.
2. **Endlichkeit**: Der Algorithmus muss nach einer endlichen Anzahl von Schritten zum Abschluss kommen.
3. **Eingabe und Ausgabe**: Ein Algorithmus verarbeitet bestimmte Eingabedaten und liefert als Ergebnis eine Ausgabe.
Nennen Sie 2 Komplexitätsklassen von Suchalgorithmen und nennen Sie jeweils Beispiel dazu
Zwei Komplexitätsklassen von Suchalgorithmen sind:
1. **Lineare Komplexität (O(n))**: Ein Beispiel dafür ist die **Lineare Suche**. Hierbei wird jedes Element der Liste einzeln durchsucht, bis das gesuchte Element gefunden wird.
2. **Logarithmische Komplexität (O(log n))**: Ein Beispiel ist die **Binäre Suche**. Diese funktioniert in sortierten Listen, bei denen die Anzahl der zu durchsuchenden Elemente in jedem Schritt halbiert wird.
Nennen Sie 2 verschiedene Klassen der O-Notation für Sortieralgorithmen und geben sie für jede Klasse 2 Beispielalgorithmen
Zwei verschiedene Klassen der O-Notation für Sortieralgorithmen sind:
1. **Quadratische Komplexität (O(n²))**:
- Bubble Sort-: Ein einfacher Sortieralgorithmus, der benachbarte Elemente wiederholt vergleicht und bei Bedarf vertauscht.
- Insertion Sort-: Ein Algorithmus, der Elemente schrittweise in eine bereits sortierte Sequenz einfügt.
2. **Logarithmische Komplexität (O(n log n))**:
- Merge Sort-: Ein Divide-and-Conquer-Algorithmus, der die Liste in kleinere Teile aufteilt, diese sortiert und dann zusammenführt.
- Quick Sort: Ein weiterer Divide-and-Conquer-Algorithmus, der ein Pivot-Element wählt und die Liste in zwei Teile teilt, die jeweils rekursiv sortiert werden.
Wie kann man den größten oder kleinsten Knoten eines Binären Suchbaums finden ? Erklären Sie
Für den kleinsten Knoten gehe wiederholt nach links.
Für den größten Knoten gehe wiederholt nach rechts.
Erläutern Sie die „Teile und Herrsche"-Methodik. Nennen Sie 2Algorithmen, die diese Methodik anwenden?
Teile und Herrsche (Divide and Conquer)
Schritte:
1. Teilen: Problem in kleinere Teilprobleme zerlegen.
2. Beherrschen: Teilprobleme rekursiv lösen.
3. Kombinieren: Teillösungen zusammenführen, um das Gesamtproblem zu lösen.
**Algorithmen**:
1.- Mergesort: Liste wird geteilt, sortiert und zusammengeführt.
Komplexität: = O(n log n)
2.-Quicksort: Pivot wählen, Liste in kleiner/größer als Pivot teilen, rekursiv sortieren.
Komplexität: Durchschnitt = O(n log n)/ schlechtester Fall = O(n^2)
Zuletzt geändertvor 4 Monaten