Kapitel 1: Einführung in Algorithmen Flashcards
Definition “Ziel eines Algorithmus”
Design und Analyse von Algorithmen, insbesondere wenn verschiedene Algorithmen das gleiche Problem lösen.
Definition Algorithmus
Ein Algorithmus ist eine definierte berechenbare Prozedur, die einen Wert oder eine Menge von Werten als Eingabedaten verarbeiten und einen Wert oder eine Menge von Werten als Ausgabewerte zurückgeben.
Wann ist ein Algorithmus korrekt ?
- für jede Eingabeinstanz der Algorithmus hält und
- wenn er hält, dann auch die korrekte Ausgabe liefert und somit das Problem löst.
Definition Datenstruktur
Eine Datenstruktur speichert und organisiert Daten und ermöglicht auf die Daten zuzugreifen und diese zu modifizieren.
Was kennzeichnet ein Array (Feld)?
- Feld von n gleichen Daten
- zusammenhängender
Speicherbereich ab einer
Startadresse - Startadresse &a[0] = Adresse
auf das 1. Datenelement - &a[1] = &a[0] +size(DS) =
Adresse auf das 2.
Datenelement - direkter Zugriff über die
entsprechende Referenz auf
jedes Datenelement im Array
Wann ist der “Insertion Sort” am schnellsten ?
Folge ist schon vorsortiert
Wie schnell ist der “Insertion Sort” in der O-Notation im Best Case ?
O(n) wenn die Folge schon vorsortiert ist
Wann ist der “Insertion Sort” am langsamsten?
Folge ist falsch herum sortiert
Wie schnell ist der “Insertion Sort” in der O-Notation im Worst Case ?
O(n^2) wemm falsch herum sortiert ist
Wann ist der “Insertion Sort” im Average Case ?
Im Mittel sind die Hälfte der Elemente kleiner als A[j] und die andere hälfte größer.
A[1…j-1]
