Suche Flashcards

1
Q

Was ist die lineare Suche?

A

Die lineare Suche ist ein einfacher Suchalgorithmus, der die Position eines Elements in einer Liste findet, indem er jedes Element der Liste nacheinander überprüft, bis das gesuchte Element gefunden wird oder das Ende der Liste erreicht ist.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Wie funktioniert die lineare Suche?

A
def lineare_suche(element, liste):
    for i in range(len(liste)):
        if element == liste[i]:
            return i
    return -1

Und hat eine Laufzeit von O(n) - Die Laufzeit ist linear in der Länge der Liste

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Was ist die binäre Suche?

A

Die binäre Suche ist ein effizienter Suchalgorithmus für sortierte Listen. Sie funktioniert, indem sie das Suchintervall in jeder Iteration halbiert. Der Algorithmus vergleicht das zu suchende Element mit dem mittleren Element der Liste. Wenn das gesuchte Element kleiner ist, wird im linken Teil weitergesucht, ansonsten im rechten Teil.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Wie funktioniert die binäre Suche?

A
def binaere_suche(element, liste):
    minIndex = 0
    maxIndex = len(liste) - 1
    while maxIndex >= minIndex:
        midIndex = minIndex + (maxIndex - minIndex) // 2
        if element > liste[midIndex]:
            minIndex = midIndex + 1
        elif element < liste[midIndex]:
            maxIndex = midIndex - 1
        else:
            return midIndex
    return -1

Und hat eine Laufzeit von O(log n) - Die Laufzeit ist logarithmisch in der Länge der Liste.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Was ist die Komplexität Konstant und was sind ihre typischen Codes?

A

Laufzeit: O(1)
Typischer Code: a = b + c
Beschreibung: Einfache Anweisung, wie das Addieren von zwei Floats
Beispiel: a = b + c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Was ist die Komplexität Logarithmisch und was sind ihre typischen Codes?

A

Laufzeit: O(log n)
Typischer Code: Siehe binäre Suche
Beschreibung: Iteratives Halbieren, wie bei der binären Suche.
Beispiel: Binäre Suche

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Was ist die Komplexität Linear und was sind ihre typischen Codes?

A

Laufzeit: O(n)
Typischer Code: for i in range(n): …
Beschreibung: Eingache Schleife,wie das Suchen nach einem Maximum
Beispiel: a = b + c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Was ist die Komplexität Quasilinear und was sind ihre typischen Codes?

A

Laufzeit: O(n log n)
Typischer Code: Siehe fortgeschrittenes Sortieren
Beschreibung: “Divide and conquer”, wie bei Mergesort.
Beispiel: MergeSort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Was ist die Komplexität Quadratisch und was sind ihre typischen Codes?

A

Laufzeit: O(n^2)
Typischer Code:

for i in range(n):
                 for j in range(n):

Beschreibung: Doppelte Schleife, wie das Vergleichen aller Paare.
Beispiel: Alle Paare vergleichen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Was ist die Komplexität Kubisch und was sind ihre typischen Codes?

A

Laufzeit: O(n^3)
Typischer Code:

for i in range(n):
      for j in range(n):
			     for k in range(n):

Beschreibung: Dreifache Schleife, wie das Vergleichen aller Tripel.
Beispiel: Alle Tripel vergleichen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Was ist die Komplexität Exponentiell und was sind ihre typischen Codes?

A

Laufzeit: O(2^n)
Typischer Code: Siehe Hanoi
Beschreibung: Verdoppelung der Arbeit, wie bei den Türmen von Hanoi.
Beispiel: Verdoppelung der Arbeit, wie bei den Türmen von Hanoi.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Erstelle eine Funktion mit der linearen Suche, um zu zählen wie oft das Element in der Liste vorkommt.

A
def suche(element, liste):
      zähler = 0
      for wort in liste:
             if element == wort:
                   zähler += 1
      return [element, zähler]						 
How well did you know this?
1
Not at all
2
3
4
5
Perfectly