Aufgabe 09 - Wachstum verstehen
Aufgabe 09 - Wachstum verstehen
Abschnitt betitelt „Aufgabe 09 - Wachstum verstehen“Worum geht es?
Abschnitt betitelt „Worum geht es?“Ohne Formeln, aber mit Verstand: Sie ordnen Alltagsalgorithmen nach ihrem Wachstumsverhalten und begründen die Einordnung (siehe Kapitel Algorithmen analysieren).
In dieser Übung üben Sie:
- Einordnen: konstantes, lineares, quadratisches und logarithmisches Wachstum unterscheiden.
- Begründen: die Einordnung am Code festmachen (Schleifenstruktur!).
- Übertragen: Konsequenzen für echte Datenmengen abschätzen.
Benötigte Unterlagen
Abschnitt betitelt „Benötigte Unterlagen“- Die Codeschnipsel unten, Papier oder Textdokument.
Arbeitsaufträge
Abschnitt betitelt „Arbeitsaufträge“Teil A - Einordnen
Abschnitt betitelt „Teil A - Einordnen“Ordnen Sie jedem Schnipsel eine Wachstumsklasse zu (konstant / logarithmisch / linear / quadratisch) und begründen Sie mit einem Satz:
liste[0] + liste[liste.length - 1]- eine einfache
for-Schleife über alle Elemente (Summe), - zwei verschachtelte Schleifen über alle Elemente (jedes Paar vergleichen),
- binäre Suche,
- zwei Schleifen hintereinander (erst Summe, dann Maximum). Achtung, ein beliebter Denkfehler!
Teil B - Hochrechnen
Abschnitt betitelt „Teil B - Hochrechnen“Ein Verfahren braucht bei 1 000 Elementen genau 1 Sekunde. Schätzen Sie die Dauer bei 10 000 und 100 000 Elementen, wenn das Verfahren (a) linear, (b) quadratisch wächst. Stellen Sie die sechs Werte in einer Tabelle gegenüber und formulieren Sie Ihre Erkenntnis in einem Satz.
Teil C - Aus dem Alltag
Abschnitt betitelt „Teil C - Aus dem Alltag“Finden Sie je ein Alltagsbeispiel (ohne Computer) für lineares, quadratisches und logarithmisches Vorgehen, z. B. rund um Namenslisten, Gruppenfotos oder Wörterbücher. Beschreiben Sie jedes in 2-3 Sätzen.
Ein Dokument (oder Markdown-Datei) mit den Teilen A-C. Wird in der Gruppe präsentiert und diskutiert.