Warum wird die App so langsam?
Deine Klassenfahrt-Gruppe hat 20 Leute. Die Anmeldeliste ist schnell durchsucht. Jetzt nutzt die ganze Schule die App, mit 1000 Namen. Plötzlich dauert alles länger.
Wie viel länger? Das kannst du vorher ausrechnen, wenn du die Schritte zählst, die ein Verfahren macht.
Das kannst du nach dieser Lektion
Notiz
Ich kann sagen, wie sich die Zahl der Schritte ändert, wenn eine Liste größer wird.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Schritt | Ein Vergleich oder eine andere kleine Handlung des Verfahrens. | |
| Aufwand | Wie viele Schritte ein Verfahren braucht. | |
| Halbieren | Die Menge in jedem Schritt auf die Hälfte verkleinern. | 1000, 500, 250 |
| Wachsen | Größer werden, zum Beispiel die Liste. | |
| Schlimmster Fall | Die Lage, in der das Verfahren am meisten Schritte braucht. |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Einstieg: Was du schon weißt
Probier es aus
Einstieg: Was du schon weißt
4 FragenDeine Antworten werden hier bewertet und nicht gespeichert. Mit einem Konto bleiben deine Ergebnisse erhalten.
Man zählt Schritte, keine Sekunden
Wie lange ein Programm in Sekunden braucht, hängt vom Gerät ab. Dein Handy ist schneller als ein altes Notebook.
Darum zählt man lieber Schritte, zum Beispiel Vergleiche. Die Zahl der Schritte ist auf jedem Gerät gleich. Und sie zeigt, wie der Aufwand wächst, wenn die Liste größer wird.
Probiere: Schritte der linearen Suche
def zaehle_schritte_suche(liste, gesucht):
schritte = 0
for zahl in liste:
schritte = schritte + 1
if zahl == gesucht:
return schritte
return schritte
for groesse in [10, 100, 1000]:
liste = []
for zahl in range(groesse):
liste.append(zahl)
# Der gesuchte Wert fehlt, also muss alles angesehen werden.
print(groesse, "Werte:", zaehle_schritte_suche(liste, -1), "Schritte")
# Ändere -1 zu 0. Wie viele Schritte braucht die Suche jetzt?
Lineare Suche: so viele Schritte wie Werte
Im schlimmsten Fall fehlt der gesuchte Wert. Dann sieht die lineare Suche jeden Wert an.
Bei 10 Werten sind das 10 Schritte, bei 100 Werten 100 Schritte. Wird die Liste zehnmal so groß, braucht die Suche zehnmal so viele Schritte.
Kurze Kontrolle
Probier es aus
Kurze Kontrolle
3 FragenDeine Antworten werden hier bewertet und nicht gespeichert. Mit einem Konto bleiben deine Ergebnisse erhalten.