Kapitel 1: Einführung in Algorithmen Flashcards Preview

Algorithmen und Datenstrukturen SS2018 > Kapitel 1: Einführung in Algorithmen > Flashcards

Flashcards in Kapitel 1: Einführung in Algorithmen Deck (10):
1

Definition "Ziel eines Algorithmus"

Design und Analyse von Algorithmen, insbesondere wenn verschiedene Algorithmen das gleiche Problem lösen.

2

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.

3

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.

4

Definition Datenstruktur

Eine Datenstruktur speichert und organisiert Daten und ermöglicht auf die Daten zuzugreifen und diese zu modifizieren.

5

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

6

Wann ist der "Insertion Sort" am schnellsten ?

Folge ist schon vorsortiert

7

Wie schnell ist der "Insertion Sort" in der O-Notation im Best Case ?

O(n) wenn die Folge schon vorsortiert ist

8

Wann ist der "Insertion Sort" am langsamsten?

Folge ist falsch herum sortiert

9

Wie schnell ist der "Insertion Sort" in der O-Notation im Worst Case ?

O(n^2) wemm falsch herum sortiert ist

10

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]