Suche Flashcards
Was ist die lineare Suche?
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.
Wie funktioniert die lineare Suche?
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
Was ist die binäre Suche?
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.
Wie funktioniert die binäre Suche?
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.
Was ist die Komplexität Konstant und was sind ihre typischen Codes?
Laufzeit: O(1)
Typischer Code: a = b + c
Beschreibung: Einfache Anweisung, wie das Addieren von zwei Floats
Beispiel: a = b + c
Was ist die Komplexität Logarithmisch und was sind ihre typischen Codes?
Laufzeit: O(log n)
Typischer Code: Siehe binäre Suche
Beschreibung: Iteratives Halbieren, wie bei der binären Suche.
Beispiel: Binäre Suche
Was ist die Komplexität Linear und was sind ihre typischen Codes?
Laufzeit: O(n)
Typischer Code: for i in range(n): …
Beschreibung: Eingache Schleife,wie das Suchen nach einem Maximum
Beispiel: a = b + c
Was ist die Komplexität Quasilinear und was sind ihre typischen Codes?
Laufzeit: O(n log n)
Typischer Code: Siehe fortgeschrittenes Sortieren
Beschreibung: “Divide and conquer”, wie bei Mergesort.
Beispiel: MergeSort
Was ist die Komplexität Quadratisch und was sind ihre typischen Codes?
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
Was ist die Komplexität Kubisch und was sind ihre typischen Codes?
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
Was ist die Komplexität Exponentiell und was sind ihre typischen Codes?
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.
Erstelle eine Funktion mit der linearen Suche, um zu zählen wie oft das Element in der Liste vorkommt.
def suche(element, liste):
zähler = 0
for wort in liste:
if element == wort:
zähler += 1
return [element, zähler] 
