Lernziele: Ausgangslage
Wir versuchen abzuschätzen, wie lange die Ausführung eines Programms, abhängig von seiner Input-Länge, dauert. Wir sprechen von der Komplexität eines Programms oder eines Algorithmus.
Wir erforschen die Komplexität am Beispiel der Suche: Gegeben sei eine Liste mit Namen.
liste = ["Finn", "Geremia", "Gian", "Janis", "Kenneth", "Max", "Pascal", "Philipp", "Roman", "Samantha", "Vincent"]Es gibt nun «intelligente» und «weniger intelligente» Möglichkeiten, diese Liste nach einem bestimmten Element zu durchsuchen.
Lineare Suche
Wir gehen die Liste Element um Element durch und vergleichen die Elemente mit dem gesuchten Element:
def lin_search(liste, search_item):
i = 1
for item in liste:
if item == search_item:
return i
i = i + 1Wir zählen wie viele Elemente wir vergleichen müssen und geben diese Zahl mit return zurück.
Der beste Fall wäre die Suche nach «Finn» – hier können wir gleich beim ersten Element die Suche abbrechen.
Der schlechteste Fall wäre die Suche nach «Vincent» – hier müssen wir alle Elemente durchgehen und werden erst beim letzten fündig. (oder gleich schlecht: die Suche nach einem Namen der gar nicht vorkommt!)
Im Durchschnitt werden wir in der Hälfte der Liste fündig!
Uns interessiert aber der schlechteste Fall! – Wenn ein Programm im Schnitt einige Sekunden benötigt, aber dann im schlechtesten Fall trotzdem ein Jahr, ist es nicht wirklich brauchbar!
Komplexität
Was ist nun, wenn wir die Liste verlängern? Dann steigt die Anzahl der Vergleiche natürlich auch: Für eine doppelt so lange Liste müssen wir auch doppelt so viele Vergleiche anstellen.
Wir haben hier also ein lineares Wachstum, welches wir in der sogenannten O-Notation wie folgt schreiben:
Die lineare Suche gehört zu den Funktionen der Klasse
Binäre Suche
Eine «intelligentere Suche» macht sich zu Nutze, dass diese Liste alphabetisch sortiert ist. Wir vergleichen unser gesuchtes Element mit dem Element in der Mitte der Liste. Kommt unser gesuchtes Element im Alphabet nach dem Element in der Mitte, so halbieren wir die Liste und gucken uns nun nur noch den zweiten Teil an. Dort wiederholen wir das Prozedere, bis wir das Element finden.
Dadurch entsteht ein sogenannter binärer Baum:
Mit jedem Vergleich halbieren wir also die Menge der in Frage kommenden Elemente. «Max» ist genau in der Mitte, «Gian» und «Roman» sind in der Mitte der beiden Hälften, usw.
Wir kommen in diesem Beispiel in maximal 4 Schritten zu unserem Ziel. (Der Baum hat 4 Ebenen)
Komplexität
Da die Liste nach jedem Aufruf halbiert wird, haben wir nach dem ersten Teilen noch
Diese Suche hat also kein lineares Verhalten mehr, sondern ein logarithmisches. Wir notieren das in der O-Notation wie folgt:
Die binäre Suche gehört zu den Funktionen der Klasse
Die binäre Suche ist also schneller als die lineare. Gerade bei längeren Listen macht sich das sehr stark bemerkbar:
| Such- | Anzahl Elemente der Liste | ||
|---|---|---|---|
| Algorithmus | 10 | 50 | n |
| linear | 10 | 50 | |
| binär | 4 | 6 | |
Natürlich muss die Liste sortiert werden, bevor die lineare Suche angewandt werden kann. Dies muss aber nur 1x geschehen, dann können beliebig viele Suchen gemacht werden.
Code
Eine Möglichkeit, die binäre Suche zu implementieren, sieht wie folgt aus:
def bin_search(liste, search_item):
i = 1
min = 0
max = len(liste)
index = (max - min) // 2
while True:
item = liste[index]
if item == search_item:
return i
elif item < search_item:
min = index
else:
max = index
index = min + (max - min) // 2
i = i + 1Es wird immer nur ein Teil der Liste durchsucht, der nach jedem Schritt kleiner wird. Der Teil der Liste wird durch die Variablen min und max eingegrenzt.
experimenteller Vergleich
Direkt-Vergleich für eine Liste
Wir wählen 10000 Mal zufällig ein Element der Liste aus und schauen wie viele Schritte die beiden Suchalgorithmen brauchen, um es zu finden. Den Durchschnitt geben wir aus.
import random
def test1():
i = 0
lin_count = 0
bin_count = 0
while i < 10000:
item = liste[random.randint(0, len(liste) - 1)]
lin_count = lin_count + lin_search(liste, item)
bin_count = bin_count + bin_search(liste, item)
i = i + 1
print("linear search: ", lin_count / i)
print("binary search: ", bin_count / i)Vergleich bei Zunahme der Listenlänge
Wir führen denselben Vergleich nun für Listen mit unterschiedlicher Länge aus: Die äussere while-Schleife sorgt dafür, dass aus der ursprünglichen Liste, unterschiedlich lange Unterlisten erstellt werden. Dazu wird die Liste «zerschnitten» mit liste[0:x]. Diese Unterliste wird immer länger, bis wir dann die Original-Liste wieder erhalten. Für jede Unterliste wird wiederum der Durchschnitt von 10000 Suchen eines zufälligen Elementes berechnet.
import matplotlib.pyplot as plt
def test2():
plot_x = []
plot_y1 = []
plot_y2 = []
x = 1
while x < len(liste):
short_liste = liste[0:x]
i = 0
lin_count = 0
bin_count = 0
while i < 10000:
item = liste[random.randint(0, len(short_liste) - 1)]
lin_count = lin_count + lin_search(short_liste, item)
bin_count = bin_count + bin_search(short_liste, item)
i = i + 1
plot_x.append(x)
plot_y1.append(count1 / i)
plot_y2.append(count2 / i)
x = x + 1
plt.plot(plot_x, plot_y1, plot_y2)
plt.show()Am Schluss sind in den Variablen plot_x, plot_y1 und plot_y2 die Ergebnisse abgespeichert. Diese können nun z.B. mit der matplotlib ausgegeben werden.
Für eine Liste bis Länge 50 führt dies zu folgendem Output:
Theorie
Algorithmen mit einer polynomialen Laufzeit von
Algorithmen mit exponentieller Laufzeit, also
Für viele Probleme der Informatik hat man noch keine effiziente Algorithmen gefunden, also solche mit polynomialer Laufzeit oder besser.
Ein solches Beispiel ist die Faktorisierung einer Zahl in ihre Primfaktoren.
Diese Aufgabe scheint einfach, wird aber für sehr grosse Zahlen sehr aufwändig!
Es ist kein polynomiales Faktorisierungsverfahren bekannt – es kann aber auch nicht ausgeschlossen werden, dass es ein solches gibt! Dieses sogenannte P-NP-Problem ist eines der grossen ungelösten Probleme der theoretischen Informatik.