Laufzeitanalyse - Versionsgeschichte

Flbkwikiadmin: /* Laufzeitanalyse von Insertion Sort */

2026-04-21T06:38:52Z

Laufzeitanalyse von Insertion Sort

← Nächstältere Version		Version vom 21. April 2026, 08:38 Uhr
Zeile 65:		Zeile 65:
	int v, i, j;		int v, i, j;
	for (i = 1; i < zSortfeld.length; i++) {		for (i = 1; i < zSortfeld.length; i++) {
	~~c++; // Zähler für Vergleiche~~
	if (zSortfeld[i] < zSortfeld[i - 1]) {		if (zSortfeld[i] < zSortfeld[i - 1]) {
	v = zSortfeld[i];		v = zSortfeld[i];

Flbkwikiadmin: /* Average-Case des Insertion Sort */

2026-04-21T06:36:28Z

Average-Case des Insertion Sort

← Nächstältere Version		Version vom 21. April 2026, 08:36 Uhr
Zeile 100:		Zeile 100:

	=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===		=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
	~~=== Average-Case des Insertion Sort ===~~
	Wir sortieren ein Array der Länge <math>n</math>. Wir nehmen an, alle Permutationen (Anordnungen) der Zahlen sind gleich wahrscheinlich. Der Algorithmus fügt nacheinander jedes Element an Index <math>i</math> (von Position 2 bis <math>n</math>) in den bereits sortierten vorderen Teil der Länge <math>i-1</math> ein.		Wir sortieren ein Array der Länge <math>n</math>. Wir nehmen an, alle Permutationen (Anordnungen) der Zahlen sind gleich wahrscheinlich. Der Algorithmus fügt nacheinander jedes Element an Index <math>i</math> (von Position 2 bis <math>n</math>) in den bereits sortierten vorderen Teil der Länge <math>i-1</math> ein.

Flbkwikiadmin: /* 3. Average-Case-Szenario (Durchschnittlicher Fall) */

2026-04-21T06:36:16Z

3. Average-Case-Szenario (Durchschnittlicher Fall)

← Nächstältere Version		Version vom 21. April 2026, 08:36 Uhr
Zeile 100:		Zeile 100:

	=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===		=== 3. Average-Case-Szenario (Durchschnittlicher Fall) ===
	~~Die Werte im~~ Array sind ~~völlig zufällig verteilt~~.		=== Average-Case des Insertion Sort ===
	* '''~~Verhalten~~:''' ~~Im Durchschnitt müssen wir ein Element nicht~~ bis ganz ~~an den Anfang schieben (wie im Worst-Case~~), ~~sondern nur bis zur~~ '''~~Hälfte~~''' des ~~bisher sortierten Bereichs~~.		Wir sortieren ein Array der Länge <math>n</math>. Wir nehmen an, alle Permutationen (Anordnungen) der Zahlen sind gleich wahrscheinlich. Der Algorithmus fügt nacheinander jedes Element an Index <math>i</math> (von Position 2 bis <math>n</math>) in den bereits sortierten vorderen Teil der Länge <math>i-1</math> ein.
	* '''~~Aufwand~~:''' Die ~~Anzahl~~ der ~~Vergleiche halbiert~~ sich ~~grob im Vergleich zum Worst-Case~~. ~~Der Aufwand liegt~~ bei ~~ca.~~ <math>\frac{1}{2} \cdot \frac{c}{2}n^2</math>.
	* '''~~Komplexität~~:''' ~~Wie wir gelernt haben, ignoriert die Groß-~~O-Notation ~~konstante Brüche~~ (wie <math>\frac{1}{4}</math>)~~. Es bleibt bei~~ der ~~höchsten Potenz: Das Wachstum ist und bleibt quadratisch. Die Komplexität lautet also weiterhin~~ <math>\mathcal{O}(n^2)</math>.		* '''Schritt 1: Wahrscheinlichkeit bestimmen.''' Beim Einfügen des <math>i</math>-ten Elements gibt es genau <math>i</math> mögliche Zielpositionen (von ganz vorne bis zu seinem aktuellen Platz ganz hinten). Da die ursprüngliche Reihenfolge zufällig ist, ist jede dieser Positionen gleich wahrscheinlich. Die Wahrscheinlichkeit für jede Position ist also <math>p = \frac{1}{i}</math>.
			* '''Schritt 2: Schritte zählen.''' Das Finden der richtigen Position ist wie eine rückwärtsgerichtete lineare Suche. Im besten Fall (das Element ist bereits größer als alle vorherigen und bleibt am Ende) brauchen wir 1 Vergleich. Im Durchschnitt muss das Element mit der Hälfte der bereits sortierten Elemente verglichen werden, um seinen Platz zu finden. Der durchschnittliche Aufwand (Vergleiche) für das Einfügen des <math>i</math>-ten Elements liegt daher bei etwa <math>\frac{i}{2}</math>.
			* '''Schritt 3: Erwartungswert berechnen.''' Um die Gesamtlaufzeit zu erhalten, summieren wir den durchschnittlichen Aufwand für alle Elemente, die eingefügt werden müssen (von <math>i=2</math> bis <math>n</math>):

			<math>E(T) \approx \sum_{i=2}^{n} \frac{i}{2}</math>

			Wir klammern <math>\frac{1}{2}</math> aus:

			<math>E(T) \approx \frac{1}{2} \cdot \sum_{i=2}^{n} i</math>

			Die Summe der Zahlen von 1 bis <math>n</math> lässt sich wieder mit der '''Gaußschen Summenformel''' (kleiner Gauß) vereinfachen zu <math>\frac{n(n+1)}{2}</math>. Da unsere Summe aber erst bei <math>i=2</math> startet, ziehen wir die 1 (für den fehlenden Schritt <math>i=1</math>) ab:

			<math>E(T) \approx \frac{1}{2} \cdot \left( \frac{n(n+1)}{2} - 1 \right) = \frac{n^2 + n - 2}{4} = \frac{1}{4}n^2 + \frac{1}{4}n - \frac{1}{2}</math>

			'''Fazit:''' Im Durchschnitt braucht der Insertion Sort etwa <math>\frac{1}{4}n^2</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{4}</math> und Terme niedrigerer Ordnung (wie <math>\frac{1}{4}n - \frac{1}{2}</math>) wegfallen, gehört der Insertion Sort im Durchschnitt zur Klasse <math>\mathcal{O}(n^2)</math>.

	[[Kategorie:Programmierung]]		[[Kategorie:Programmierung]]
	[[Kategorie:AHR_I_Informatik_LK]]		[[Kategorie:AHR_I_Informatik_LK]]

Flbkwikiadmin: /* Mathematische Berechnung des Average-Case */

2026-04-21T06:32:27Z

Mathematische Berechnung des Average-Case

← Nächstältere Version		Version vom 21. April 2026, 08:32 Uhr
Zeile 29:		Zeile 29:
	Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:		Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert <math>E(T)</math> lautet:

	<math>E(T) = \sum_{i=1}^{\|E\|} p_i \cdot t_i</math>		<math>E(T) = \sum_{i=1}^{\|F\|} p_i \cdot t_i</math>

	Hierbei bedeuten die Variablen:		Hierbei bedeuten die Variablen:
	* <math>E</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).		* <math>F</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).
	* <math>\|E\|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.		* <math>\|F\|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.
	* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.		* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.
	* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.		* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.

Flbkwikiadmin am 20. April 2026 um 10:26 Uhr

2026-04-20T10:26:00Z

← Nächstältere Version		Version vom 20. April 2026, 12:26 Uhr
Zeile 31:		Zeile 31:
	<math>E(T) = \sum_{i=1}^{\|E\|} p_i \cdot t_i</math>		<math>E(T) = \sum_{i=1}^{\|E\|} p_i \cdot t_i</math>

	* <math>p_i</math> ist die Wahrscheinlichkeit ~~für einen bestimmten Fall~~ <math>i</math>.		Hierbei bedeuten die Variablen:
	* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus ~~in diesem Fall~~ braucht.		* <math>E</math> ist die Menge aller theoretisch möglichen Eingaben der Größe <math>n</math> (z. B. alle möglichen Anordnungen einer Zahlenliste).
			* <math>\|E\|</math> (Betragsstriche) steht in der Mathematik für die Mächtigkeit einer Menge. Es ist also die '''exakte Anzahl''' aller dieser möglichen Eingaben.
			* <math>p_i</math> ist die Wahrscheinlichkeit, dass genau die spezifische Eingabe <math>i</math> auftritt.
			* <math>t_i</math> ist die Anzahl der Rechenschritte, die der Algorithmus für exakt diese Eingabe <math>i</math> braucht.

	Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder ~~Fall~~ tritt mit derselben Wahrscheinlichkeit auf.		Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Eingabefall tritt mit exakt derselben Wahrscheinlichkeit auf.

	=== Average-Case der Linearen Suche ===		=== Average-Case der Linearen Suche ===

Flbkwikiadmin am 20. April 2026 um 07:39 Uhr

2026-04-20T07:39:06Z

← Nächstältere Version		Version vom 20. April 2026, 09:39 Uhr
Zeile 54:		Zeile 54:

	'''Fazit:''' Im Durchschnitt braucht die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{2}</math> wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse <math>\mathcal{O}(n)</math>.		'''Fazit:''' Im Durchschnitt braucht die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{2}</math> wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse <math>\mathcal{O}(n)</math>.

	~~=== Maximumsuche ===~~
	Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem mathematischen Trick: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu verstehen, analysieren wir einen simplen Code zur Maximumsuche:

	~~<syntaxhighlight lang="java">~~
	~~public int findMax(int[] A) {~~
	~~int max = A[0];~~
	~~for (int i = 1; i < A.length; i++) {~~
	~~if (A[i] > max) {~~
	~~max = A[i]; // Update-Operation~~
	}
	}
	~~return max;~~
	}
	~~</syntaxhighlight>~~
	~~Die Vergleiche in der <code>if</code>-Bedingung werden immer <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt überschrieben (Update-Operation)?~~

	~~Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.~~
	* '''Intuitiver Ansatz:'''
	~~Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1).~~
	~~Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist exakt 50% (<math>\frac{1}{2}</math>).~~
	~~Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist <math>\frac{1}{3}</math>.~~

	* '''Mathematischer Ansatz (Indikatorvariablen):'''
	Wir definieren einen „Schalter“ (die Indikatorvariable) <math>X_i</math>. Er ist <math>1</math>, wenn ein neues Maximum an Stelle <math>i</math> gefunden wird, sonst <math>0</math>. Die Wahrscheinlichkeit dafür ist <math>P(X_i = 1) = \frac{1}{i}</math>.

	~~Um die durchschnittliche Gesamtzahl der Updates zu finden, addieren wir einfach diese Wahrscheinlichkeiten auf:~~

	~~<math>E[X] = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{n}</math>~~

	Diese spezielle Summe nennt man in der Mathematik die '''Harmonische Reihe''' (<math>H_n</math>). Sie wächst extrem langsam. Für große Zahlen <math>n</math> entspricht sie in etwa dem '''natürlichen Logarithmus''' (<math>\ln(n)</math>).

	'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.

	== Laufzeitanalyse von Insertion Sort ==		== Laufzeitanalyse von Insertion Sort ==

Flbkwikiadmin am 20. April 2026 um 07:35 Uhr

2026-04-20T07:35:10Z

← Nächstältere Version		Version vom 20. April 2026, 09:35 Uhr
Zeile 36:		Zeile 36:
	Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Fall tritt mit derselben Wahrscheinlichkeit auf.		Für die Schule gehen wir meistens von einer '''Gleichverteilung''' aus: Jeder Fall tritt mit derselben Wahrscheinlichkeit auf.

	=== ~~Beispiel 1:~~ Average-Case der Linearen Suche ===		=== Average-Case der Linearen Suche ===
	Wir suchen eine bestimmte Zahl in einem Array der Länge <math>n</math>. Wir nehmen an, die Zahl ist im Array und jede Position ist gleich wahrscheinlich.		Wir suchen eine bestimmte Zahl in einem Array der Länge <math>n</math>. Wir nehmen an, die Zahl ist im Array und jede Position ist gleich wahrscheinlich.

Zeile 88:		Zeile 88:
	'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.		'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.

	== ~~Beispiel 3:~~ Laufzeitanalyse von Insertion Sort ==		== Laufzeitanalyse von Insertion Sort ==
	Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort\|Insertion Sort]] (Sortieren durch Einfügen) an.		Nun wenden wir unser Wissen auf das Sortierverfahren [[Insertion-sort\|Insertion Sort]] (Sortieren durch Einfügen) an.

Flbkwikiadmin: /* Beispiel 2: Vorbereitung auf Quicksort (Maximumsuche) */

2026-04-20T07:34:36Z

Beispiel 2: Vorbereitung auf Quicksort (Maximumsuche)

← Nächstältere Version		Version vom 20. April 2026, 09:34 Uhr
Zeile 55:		Zeile 55:
	'''Fazit:''' Im Durchschnitt braucht die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{2}</math> wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse <math>\mathcal{O}(n)</math>.		'''Fazit:''' Im Durchschnitt braucht die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Da in der <math>\mathcal{O}</math>-Notation Konstanten wie <math>\frac{1}{2}</math> wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse <math>\mathcal{O}(n)</math>.

	=== ~~Beispiel 2: Vorbereitung auf Quicksort (~~Maximumsuche) ===		=== Maximumsuche ===
	Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem mathematischen Trick: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu verstehen, analysieren wir einen simplen Code zur Maximumsuche:		Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem mathematischen Trick: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu verstehen, analysieren wir einen simplen Code zur Maximumsuche:

Zeile 87:		Zeile 87:

	'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.		'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.


	== Beispiel 3: Laufzeitanalyse von Insertion Sort ==		== Beispiel 3: Laufzeitanalyse von Insertion Sort ==

Flbkwikiadmin am 20. April 2026 um 07:34 Uhr

2026-04-20T07:34:12Z

Änderungen zeigen

Flbkwikiadmin am 20. April 2026 um 07:32 Uhr

2026-04-20T07:32:07Z

Änderungen zeigen