Diese Karte erklärt, wie sich der berechne den Aufwand eines Algorithmus: wie viele Operationen er in Abhängigkeit von der Größe der Daten ausführt, n, und wie er wächst, wenn n wächst.
Der Aufwand ist eine Funktion von n. Sekunden hängen vom Computer ab; Operationen nicht.
Drücke auf jeden Kasten, um seine Erklärung zu sehen. Die Pfeile ← → (oder die Schaltflächen unten) gehen zum nächsten und Esc schließt es. Sobald du es gesehen hast, erscheint ein ✓; drücke darauf, um es zu entfernen. Die Kästen mit «?» gehören zu anderen Stufen.
Diese Karte erklärt, wie sich der berechne den Aufwand eines Algorithmus: wie viele Operationen ein Programm ausführt. Jeder Kasten hat eine kurze Erklärung und in manchen Fällen eine Übung.
Ein Algorithmus ist schnell wenn er weniger Operationen.
Drücke auf jeden Kasten, um seine Erklärung zu sehen. Die Pfeile ← → gehen zum nächsten und Esc schließt es. Sobald du es gesehen hast, erscheint ein ✓.
9. Klasse ESO (für Fortgeschrittene). Vereinfachte Fassung: Rechenregeln, Ordnung in Bezug auf n und Binärsuche. Ohne formale O(·)-Notation, ohne Algorithmendiagramme und ohne den Operationskasten.
Passt zu: Digitalisierung 9. Klasse (computationales Denken: Kriterien 3.1 und 3.2, logische und effiziente Algorithmen).
Vorgeschlagene Aktivität: die Operationen einer Schleife zählen und dann mit der Binärsuche prüfen, wie viele Schritte sie macht.
PTD-I · 1. Bachillerato. Hinzu kommen die Rechenregeln (Folge, Bedingung und Schleife), die O(·)-Notation, die Wachstums- und Zeitdiagramme, die lineare Suche und die Auswahlsortierung. Die Zeitexperimente (ms) stehen nicht mehr im Mittelpunkt: gemessen wird die Anzahl der Operationen.
Passt zu: Programmierung und Datenverarbeitung I: CEsp1 (Analyse und Entwurf von Algorithmen, Kriterium 1.3 zum rechnerischen Aufwand) und CEsp3 (Effizienz und Komplexität von Operationen auf Datenstrukturen).
Vorgeschlagene Aktivität: bei 10⁹ Operationen pro Sekunde und n = 10⁶ berechnen, wie lange die lineare Suche (n) und die Blasensortierung (n(n−1)/2) brauchen, und das mit dem Zeitdiagramm vergleichen.
PTD-II · 2. Bachillerato. Gleicher Inhalt wie PTD-I: Rechenregeln, O(·)-Notation, Wachstumsdiagramme und die Such- und Sortieralgorithmen.
Passt zu: Programmierung und Datenverarbeitung II: CEsp1 (Algorithmen und computationales Denken).
Vorgeschlagene Aktivität: die lineare Suche und die Binärsuche mit n = 1 000 000 von Hand vergleichen und den Unterschied begründen.
Die Kästen mit «?» sind auf dieser Stufe verborgen: ein Klick deckt sie auf und zeigt ihren Zusammenhang, ein weiterer öffnet das Fenster, und nachdem man es gesehen hat, verbirgt ein weiterer Klick sie wieder. Die Schaltfläche 🔗 kopiert einen Link mit der Stufe und den aufgedeckten Kästen.
Der Auswähler Stufe ändert die Karte und alle Fenster. In der Adresse wird die Stufe gespeichert (?edad=4eso, ptd1 oder ptd2) und die aufgedeckten Kästen (&ver=casos,fonts).
Wenn wir sagen, ein Algorithmus sei schnell, müssen wir sagen, wobei. Sekunden hängen vom Rechner, vom System und vom gerade Laufenden ab. Deshalb zählen wir Operationen.
Wenn du zwei Algorithmen vergleichst, frage dich: was wächst und wie stark?
Der rechnerische Aufwand misst die Arbeit eines Programms in Abhängigkeit von der Größe der Daten (n. Achte auf zwei Dinge: den Zeit (Anzahl der Operationen) und die Speicher (wie viel Platz sie braucht).
Der rechnerische Aufwand eines Algorithmus ist die Anzahl derelementare Operationen macht, in Abhängigkeit von der Größe der Daten, n. Sekunden hängen vom Computer ab; Operationen nicht.
Eine elementare Operation (Zuweisung, Addition, Vergleich oder Zugriff auf eine Position) kostet 1. Gezählt wird der schlechtester Fall, was das Ergebnis für jedes beliebige Datum garantiert.
| Funktion T(n) | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| n | 10 | 1 000 | 1 000 000 |
| n² | 100 | 1 000 000 | 1 000 000 000 000 |
Sekunden taugen nicht zum Vergleichen von Algorithmen. Zähle Operationen und schau, wie wachsen wenn n wächst.
Die Größe n. Alle Formeln hängen von einer Größe ab, n: die Anzahl der Daten, die der Algorithmus erhält. Lege n fest, bevor du zählst (Anzahl der Elemente, Ziffern oder Zeilen, je nach Problem).
Ein Programm führt Anweisungen nacheinander aus. Um den Aufwand zu berechnen, addiere die Anweisungen. Gibt es eine Schleife, multipliziere mit der Anzahl der Wiederholungen.
Eine einfache Anweisung kostet 1. Eine Schleife multipliziert den Aufwand ihres Körpers mit der Anzahl der Wiederholungen.
Ein Programm kombiniert vier Strukturen. Der Gesamtaufwand wird berechnet, indem man auf jede eine Regel anwendet.
| Struktur | Aufwandsregel | Beispiel |
|---|---|---|
| Einfache Anweisung | 1 | x ← x + 1 → 1 |
| Folge | Summe der Aufwände | A; danach B → T(A) + T(B) |
| Bedingung | Test + der teuerste Zweig | wenn … dann … sonst … → 1 + max(T₁, T₂) |
| Schleife | Iterationen × Aufwand des Körpers | für i von 1 bis n: x ← x + 1 → n |
Wenn du nicht weißt, welcher Zweig einer Bedingung ausgeführt wird, nimm den teuersten: das ist der schlechtester Fall.
Der Aufwand einer Schleife ist der Aufwand ihres Körpers mal der Anzahl der Wiederholungen. Eine Operation fällt nicht auf; eine Million schon.
| Struktur | Operationen mit n = 1 000 | Operationen mit n = 1 000 000 |
|---|---|---|
| Eine Schleife | 1 000 | 1 000 000 |
| Zwei verschachtelte Schleifen | 1 000 000 | 1 000 000 000 000 |
Zähle, wie oft der innerste Körper ausgeführt wird. Eine Schleife mit n Schritten macht n Operationen; zwei verschachtelte Schleifen mit n Schritten machen n · n.
Zwei verschachtelte Schleifen sind O(n²); eine Schleife, O(n).
Eine Struktur, die einfach aussieht («es ist nur eine Schleife»), kann eine Suche darin verbergen. Schau immer nach, was in der Schleife steht.
Eine Schleife wiederholt ihren Körper. Der Gesamtaufwand ist der Aufwand des Körpers mal die Anzahl der Wiederholungen.
| Struktur | Operationen mit n = 1 000 | Operationen mit n = 1 000 000 |
|---|---|---|
| Eine Schleife | 1 000 | 1 000 000 |
| Zwei verschachtelte Schleifen (n · n) | 1 000 000 | 1 000 000 000 000 |
| Zwei Schleifen, die zweite bis i | 500 500 | 500 000 500 000 |
Eine Schleife ist O(n). Zwei verschachtelte Schleifen sind O(n²). Verschachtelte Schleifen, die bis i laufen, machen n(n+1)/2 Schritte: auch O(n²), weil wir die Konstante ½ ignorieren.
Eine Struktur, die einfach aussieht («es ist nur eine Schleife»), kann eine Suche darin verbergen. Schau immer nach, was in der Schleife steht.
Die Blasensortierung vergleicht Nachbarn und tauscht sie, wenn sie falsch stehen. Sie wiederholt Durchgänge, bis kein Tausch mehr nötig ist. Sie ist der typische Algorithmus, um den Aufwand zu verstehen, weil man alles zählen kann.
| n (Daten) | Vergleiche (schlechtester Fall) | Tausche (Durchschnitt) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Jeder Durchgang setzt den größten Wert ans Ende. Bei n Daten macht der erste Durchgang n−1 Vergleiche, der nächste n−2, und so weiter bis 1. Insgesamt im schlechtesten Fall: n(n−1)/2.
Beachte: wenn du die Daten mit 10 multiplizierst, wird die Arbeit mit 100.
Das ist O(n²). Die Vergleiche wachsen wie das Quadrat von n.
Die Blasensortierung vergleicht jedes Nachbarpaar und tauscht die, die falsch stehen. Nach jedem Durchgang steht der größte Wert am Ende.
| n (Daten) | Vergleiche (schlechtester Fall) | Tausche (Durchschnitt) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Der erste Durchgang macht n−1 Vergleiche, der zweite n−2, und so weiter bis 1. Insgesamt im schlechtesten Fall: (n−1) + (n−2) + … + 1 = n(n−1)/2, das heißt O(n²).
Zeitdiagramm: Die Zeit ist proportional zur Anzahl der Operationen. Bei 10⁹ Operationen pro Sekunde brauchen 10⁶ Operationen 1 ms.
Wenn die Liste sortiert ist, musst du nicht alles ansehen. Du schaust in die Mitte und verwirfst die Hälfte, die das Gesuchte nicht enthalten kann. Jeder Schritt halbiert die Größe.
Die Liste ist 1, 2, 3… n: Sie muss nicht vollständig im Speicher liegen, deshalb kann man mit 1 000 000 000 testen.
| n (Daten) | Binärschritte (schlechtester Fall) | Vergleiche linear (schlechtester Fall) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Jeder Schritt macht einen Vergleich und entfernt die Hälfte. Die Schritte sind ungefähr log₂ n. Deshalb brauchen 1 000 000 000 Daten nur 30 Schritte.
Das ist O(log n).
Die Binärsuche funktioniert nur, wenn die Liste sortiert. Sie zu sortieren hat ebenfalls einen Aufwand.
Die Binärsuche schaut in die Mitte der sortierten Liste und verwirft die Hälfte, die das Gesuchte nicht enthalten kann. Jeder Schritt halbiert.
Die Liste ist 1, 2, 3… n. Es werden nur die Schritte gezählt: Man muss sie nicht im Speicher halten.
| n (Daten) | Schritte (schlechtester Fall) | Lineare Suche (schlechtester Fall) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Jeder Schritt halbiert die Größe: nach k Schritten bleiben n / 2ᵏ Elemente. Da n / 2ᵏ = 1 ist, wenn k = log₂ n, beträgt der Aufwand O(log n).
Die Binärsuche funktioniert nur, wenn die Liste sortiert. Sie zu sortieren hat ebenfalls einen Aufwand.
Zeitdiagramm: Die Zeit ist proportional zur Anzahl der Operationen. Bei 10⁹ Operationen pro Sekunde brauchen 10⁶ Operationen 1 ms.
Wenn die Daten wachsen, wächst der Aufwand in einem bestimmten Tempo. Die Notation O(·) behält nur diesen Rhythmus und ignoriert die Konstanten.
O(log n) wächst sehr langsam: wenn n von 1 auf 20 steigt, erreicht es nur ≈ 4,3, während O(n) 20 erreicht.
Bei kleinem n liegen alle Kurven nah beieinander; ab n ≈ 10 löst sich die quadratische von den anderen.
| Funktion | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ≈ 33 | ≈ 10 000 | ≈ 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
O(1): der Aufwand hängt nicht von n ab. O(log n): jeder Schritt halbiert (Binärsuche). O(n): proportional zu n (lineare Suche). O(n log n): typisch für gute Sortieralgorithmen. O(n²): zwei verschachtelte Schleifen (Blasen-, Auswahlsortierung).
Wenn n mit 10 multipliziert wird: bei O(n) wird der Aufwand mit 10 multipliziert; bei O(n²) mit 100; bei O(log n) ändert er sich kaum.
Ignoriere Konstanten und kleine Terme: 3n² + 5n ist O(n²).
Die Ordnung in Bezug auf n erklärt, wie der Aufwand wächst, wenn die Daten wachsen. Es ist die wichtigste Idee dieser Karte.
Wenn n mit 10 multipliziert wird, wird ein Aufwand O(n) ebenfalls mit 10 multipliziert, ein Aufwand O(n²) aber mit 100.
Wenn der Aufwand O(n) ist, wächst die Arbeit gleich schnell wie die Daten. Wenn er O(n²) ist, vervierfacht sich die Arbeit bei doppelten Daten.
Wichtig ist wie er wächst, nicht die genaue Anzahl der Operationen.
Derselbe Algorithmus kann je nach Daten mehr oder weniger Zeit brauchen. Deshalb unterscheidet die Analyse drei Fälle: besser, Durchschnitt und schlechtester.
| Fall | Blasensortierung | Binär |
|---|---|---|
| Bester | n−1 Vergleiche (bereits sortierte Liste) | 1 Schritt (die Mitte ist die gesuchte) |
| Durchschnitt | ≈ n²/2 Vergleiche | ≈ log₂ n Schritte |
| Schlechtester | n(n−1)/2 Vergleiche | ⌊log₂ n⌋ + 1 Schritte |
Liegt der Quotient nahe bei 2, ist das Wachstum ungefähr linear; liegt er nahe bei 4, quadratisch. Das Rauschen des Browsers macht es nicht exakt: deshalb wird der Median aus 3 Wiederholungen gebildet.
Um einen Algorithmus zu beurteilen, muss man die Daten von schlechtester Fall (diejenigen, die ihn am meisten fordern), aber auch der Durchschnittsfall, der meist der häufigste ist.
Eine einzige Messung eines bestimmten Falls sagt nicht, welcher der schlechteste ist. Analysiere den Fall und miss dann.
Die lineare Suche prüft die Elemente nacheinander, bis sie findet, was du suchst. Sie ist die einfachste Methode und dient als Vergleich zur Binärsuche.
Jedes Element wird mit dem gesuchten Wert verglichen, bis er gefunden wird oder das Ende erreicht ist.
| Fall | Vergleiche | Mit n = 1 000 000 |
|---|---|---|
| Bester (es ist das erste) | 1 | 1 |
| Durchschnitt (es ist in der Mitte) | n / 2 | 500 000 |
| Schlechtester (er ist der letzte oder fehlt) | n | 1 000 000 |
Der Aufwand ist O(n): jedes Element wird höchstens einmal geprüft.
Wenn du einen Aufwand angibst, sag welcher Fall ist: der beste, der durchschnittliche oder der schlechteste.
Zeitdiagramm: Die Zeit ist proportional zur Anzahl der Operationen. Bei 10⁹ Operationen pro Sekunde brauchen 10⁶ Operationen 1 ms.
Die Auswahlsortierung sucht das Minimum des unsortierten Teils und setzt es nach vorn. Wiederhole dies, bis die ganze Liste sortiert ist.
Der erste Durchgang sucht das Minimum unter n Elementen (n−1 Vergleiche) und setzt es an die erste Stelle. Der nächste sucht unter n−1 Elementen, und so weiter bis zum letzten.
| n (Daten) | Vergleiche (immer) |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
Gesamt: (n−1) + (n−2) + … + 1 = n(n−1)/2, das heißt O(n²) in allen Fällen. Er macht höchstens n−1 Tausche.
Die Auswahlsortierung macht immer dieselben Vergleiche; die Blasensortierung kann früher aufhören, wenn die Liste bereits sortiert ist.
Zeitdiagramm: Die Zeit ist proportional zur Anzahl der Operationen. Bei 10⁹ Operationen pro Sekunde brauchen 10⁶ Operationen 1 ms.
Die Einfügesortierung nimmt jedes Element und setzt es an seine richtige Stelle im bereits sortierten Teil.
Im schlechtester Fall (umgekehrte Liste) macht n(n−1)/2 Vergleiche: O(n²). Im bester Fall (bereits sortierte Liste) macht nur n−1: O(n).
Die Einfügesortierung ist schnell, wenn die Liste bereits fast sortiert ist.
Die Mischsortierung teilt die Liste in zwei Hälften, sortiert jede Hälfte und fügt sie dann zusammen.
Jede Teilungsebene macht n Schritte und es gibt log₂ n Ebenen. Der Aufwand beträgt O(n log n) in allen Fällen.
Bei großen Listen ist sie viel schneller als die Blasensortierung.
Messen ist leicht falsch zu machen. Das sind die häufigsten Fehler und wie man sie vermeidet.
Bevor du sagst, dass ein Algorithmus schneller ist, frage dich: mit welchen Daten, auf welchem Rechner und wie oft ich gemessen habe.
Lies jede Situation und wähle welches Konzept erklärt den Fall. Wenn du einen wählst, der auch dazugehört, aber nicht der Hauptfall ist, sagen wir es dir.
Ein Programm addiert 1 000 000 Zahlen in einer Schleife. Welches Konzept erklärt, warum der Aufwand hoch ist?
Ein Programm addiert 1 000 000 Zahlen in einer Schleife. Welches Konzept erklärt, warum der Aufwand hoch ist?
Du suchst die Zahl 42 in einer sortierten Liste mit einer Million Zahlen. Du schaust in die Mitte, verwirfst die Hälfte und findest sie in etwa 20 Schritten. Welcher Algorithmus ist das?
Ein Algorithmus durchläuft die Liste, vergleicht Nachbarn und tauscht sie. Bei der umgekehrten Liste macht er n(n−1)/2 Vergleiche. Welcher Algorithmus ist das?
Ein Algorithmus braucht 4-mal so lange, wenn du die Daten verdoppelst. Welches Konzept beschreibt, wie sein Aufwand wächst?
Du suchst eine Zahl in einer unsortierten Liste mit n Elementen und vergleichst sie mit jedem Element, bis du sie findest. Welcher Algorithmus ist das?
Ein Algorithmus sucht das Minimum des unsortierten Teils und stellt es nach vorn. Er macht n(n−1)/2 Vergleiche, auch wenn die Liste bereits sortiert ist. Welcher Algorithmus ist das?
Diese Karte vereint klassische Konzepte der Algorithmenanalyse und die Lernziele des Lehrplans der Balearen. Hier kannst du es überprüfen und vertiefen.