Lernziele: Komplexität

Sie wissen…

was ein Suchalgorithmus ist

was ein Sortieralgorithmus ist und wieso diese wichtig sind

Sie kennen…

die lineare und die binäre Suche

den Bubble Sort, Selection Sort und den Quick Sort

Sie können…

das Verhalten eines Algorithmus in O-Notation beschreiben und erklären

die oben genannten Algorithmen erklären und in einem Beispiel auf Papier durchspielen

die Begriffe Zeit- und Speicherkomplexität erläutern

mit den Begriffen best case, average case und worst case argumentieren

die Eigenschaften in-place, stabil und rekursiv von Sortieralgorithmen verwenden

Aufgabe: Suche

Gegeben sei die untenstehende Tabelle

1. Suchen Sie das Medikament «Floxal», einmal mit linearer Suche und dann nocheinmal mit binärer Suche. Wie viele Vergleiche/Schritte braucht die Suche jeweils?

2. notieren Sie für die beiden Suchen nach einem Medikament-Name best case, average case und worst case

3. Suchen Sie das Medikament mit der Nummer 95031, wiederum mit linearer Suche und mit binärer Suche. Wie viele Vergleiche/Schritte braucht die Suche jeweils?

Infekte

Medikament	Nummer
AciVision Rp	43821
Azyter Augentropfen	90756
Berberil Dry Eye	16493
Berberil N	58207
Dexa-Gentamicin1	73165
Dexagent-Ophtal1	29584
Dexamytrex	84612
Euphrasia Augentropfen	50379
Floxal	17840
Gentamicin-POS	66428
Gent-Ophtal	91237
Isopto-Max1	25716
Kanamycin-POS	48905
Ofloxacin-ophtal	73592
Otobacid N1	60174
Otodolor direkt	32489
Posifenicol C	95031
Posiforlid COMOD	21768
Posiformin 2%	57643
Virupos	80325

4. Nennen Sie je einen Vor- und einen Nachteil der binären Suche gegenüber der linearen Suche

Aufgabe: Sortieren

1. Sortieren Sie die Liste [20, 10, 5, 2] mit Bubble Sort. Notieren Sie alle Zwischenschritte.

2. Sortieren Sie die Liste [20, 10, 5, 2] mit Selection Sort. Notieren Sie alle Zwischenschritte.

3. Sortieren Sie die Liste [20, 10, 5, 2] mit Quick Sort. Notieren Sie alle Zwischenschritte.

Aufgabe: Komplexität

Wieso gibt es neben Zeitkomplexität auch eine Speicherkomplexität?

Aufgabe: O-Notation

Notieren Sie zu jedem Unterprogramm den Wert von count beim return in Abhängigkeit von n.

Schreiben Sie dann die Komplexität in O-Notation.

def aufgabe_a(n):
    count = 7
    for i in range(n):
        count = count + 2
    return count

def aufgabe_b(n):
    count = 0
    for i in range(n):
        count = count + 1
        for j in range(n):
            count = count + 1
    return count

def aufgabe_c(n):
    count = 0
    i = 1
    while i < n:
        count = count + 1
        i = i * 2
    return count

Lösung: O-Notation

1. count = 7 + 2n
   «linear» -> O(n)

2. count = 0 + n + n²
   «quadratisch» -> O(n²)

3. count = ?
   «logarithmisch» -> O(log n)