Laufzeit von Algorithmen - Versionsgeschichte

Akaibel: /* Grundidee */

2019-06-23T13:43:07Z

Grundidee

← Nächstältere Version		Version vom 23. Juni 2019, 13:43 Uhr
Zeile 2:		Zeile 2:
	[[Kategorie:Algorithmen]]		[[Kategorie:Algorithmen]]
	[[Kategorie:Informatik-Abitur]]		[[Kategorie:Informatik-Abitur]]

			=Fachbegriffe=

			best case, average case, worst case, Operation, Landau-Klasse

	=Grundidee=		=Grundidee=

	Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint.		Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint.

Akaibel am 28. November 2016 um 15:25 Uhr

2016-11-28T15:25:39Z

← Nächstältere Version		Version vom 28. November 2016, 15:25 Uhr
Zeile 6:		Zeile 6:
	Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint.		Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint.

	Stattdessen wird die '''Menge der Operationen''' abgeschätzt, ~~die notwendig sind, um~~ die der Algorithmus braucht. Dabei ~~gilt~~ folgende vereinfachende Grundannahmen:		Stattdessen wird die '''Menge der Operationen''' abgeschätzt, die der Algorithmus braucht. Dabei gelten folgende vereinfachende Grundannahmen:
	* Die Anzahl der Operationen wird bestimmt in Abhängigkeit von der Größe des Problems, d.h. ~~die Laufzeit ist in~~ der ~~Regel eine Funktion~~.		* Die Anzahl der Operationen wird bestimmt in Abhängigkeit von der Größe des Problems, z.B. der Anzahl der Elemente.
			* Jede Operation gilt als gleich "teuer".
	* In der Regel reicht es, die am häufigsten vorkommende Operation abzuschätzen - oft fallen die anderen Operationen nicht ins Gewicht.		* In der Regel reicht es, die am häufigsten vorkommende Operation abzuschätzen - oft fallen die anderen Operationen nicht ins Gewicht.
	* Jede Operation gilt als gleich "teuer".

			Die Algorithmen lassen sich - gemäß ihrer Laufzeit - in verschiedene Klassen, die sogenannten [[Landau-Klassen]] einteilen.

			=Best Case - Average Case – Worst Case=

			Bei der Abschätzung der Laufzeit von Algorithmen werden in der Regel drei Fälle unterschieden:

			* Der '''Best Case''' ist eine Situation, in der man die Lösung schnellstmöglichst finden kann.
			* Der '''Average Case''' ist der durchschnittliche Fall; oft ermittelt man den Average Case aus einem Mittelwert von zufälligen Situationen.
			* Der '''Worst Case''' ist die schlimmste anzunehmende Situation.

	~~Die Algorithmen lassen sich - gemäß ihrer Laufzeit - in verschiedene Klassen, die sogenannten [[Landau-Klassen]] einteilen~~.		In der Praxis sind im Allgemeinen nur der Worst Case und der Average Case interessant.

	=Vorgehensweise=		=Vorgehensweise=
	In der Regel ist es hilfreich, erst die Laufzeit für eine ~~vorgegebene~~ Größe des Problems (z.B. 1000) zu bestimmen.		In der Regel ist es hilfreich, erst die Laufzeit für eine feste Größe des Problems (z.B. 1000) zu bestimmen.

	Dann schließt man auf die Laufzeit des Problems allgemein.		Dann schließt man auf die Laufzeit des Problems allgemein.
Zeile 25:		Zeile 34:

	==Berechnung der Laufzeit für 1000 Elemente==		==Berechnung der Laufzeit für 1000 Elemente==
	Die häufigste vorkommende Operation bei Insertionsort ist der Vergleich; nur dieser wird hier abgeschätzt.		Die häufigste vorkommende Operation bei Insertionsort ist der Vergleich; nur dieser wird hier für den Worst Case abgeschätzt.

	{\| class="wikitable"		{\| class="wikitable"
	\|+ Notwendige Vergleiche für jedes Element		\|+ Notwendige Vergleiche für jedes Element
	! Element Nr. !! Anzahl Vergleiche beim Einfügen		! Element Nr. !! Anzahl Vergleiche beim Einfügen in die Ergebnisliste<br/>''im Worst Case''
	\|-		\|-
	\| 1 \|\| 0		\| 1 \|\| 0

Akaibel am 28. November 2016 um 15:17 Uhr

2016-11-28T15:17:15Z

← Nächstältere Version		Version vom 28. November 2016, 15:17 Uhr
Zeile 1:		Zeile 1:
			[[Kategorie:Informatik]]
			[[Kategorie:Algorithmen]]
			[[Kategorie:Informatik-Abitur]]

	=Grundidee=		=Grundidee=
	Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint.		Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint.
Zeile 16:		Zeile 20:

	=Beispiel: Insertionsort=		=Beispiel: Insertionsort=
	Bei Insertionsort wird die Ergebnisliste nach und nach aufgebaut.		Bei [[Insertionsort]] wird die Ergebnisliste nach und nach aufgebaut.

	Dazu wird jeweils das erste Element aus der ursprünglichen Liste genommen und gelöscht. Dann wird die Ergebnisliste von vorne bis zu der Stelle durchlaufen, an der das Element eingefügt werden muss; da wird es dann eingefügt.		Dazu wird jeweils das erste Element aus der ursprünglichen Liste genommen und gelöscht. Dann wird die Ergebnisliste von vorne bis zu der Stelle durchlaufen, an der das Element eingefügt werden muss; da wird es dann eingefügt.

Akaibel: /* Berechnung der Laufzeit für 1000 Elemente */

2016-11-28T15:14:39Z

Berechnung der Laufzeit für 1000 Elemente

← Nächstältere Version		Version vom 28. November 2016, 15:14 Uhr
Zeile 41:		Zeile 41:

	'''Gesamtzahl der notwendigen Vergleiche'''		'''Gesamtzahl der notwendigen Vergleiche'''
	Insgesamt braucht man also <math>1+2+...+998+999 = {{999 \times 1000} \over {2}} = 499.500</math> Vergleiche.
			Insgesamt braucht man also 1+2+...+998+999 Vergleiche.

			''Um das zu berechnen, braucht man die folgende mathematische Formel, die in der Informatik einfach ohne Herleitung verwendet wird:''
			<math>1+2+...+x = {{x \times {(x+1)}} \over {2}}</math>

			Anwendung der Formel:

			<math>1+2+...+998+999 = {{999 \times 1000} \over {2}} = 499.500</math>
			Vergleiche.



			==Berechnung der Laufzeit für '''n''' Elemente==
			'''In der Formel oben wird jetzt einfach 1000 ersetzt durch n.'''

			Entsprechend ist 999 dann (n-1).

			Für n Elemente braucht man also
			<math>1+2+...+(n-2)+(n-1) = {{(n-1) \times n} \over {2}} = {{n^2} \over 2} - {n \over 2}</math>
			Vergleiche.

			Der lineare Teil ( -n/2 ) ist für große n kaum von Bedeutung.

			Deswegen gehört Insertionsort zur [[Landau-Klassen\|Landau-Klasse]] '''O'''(n<sup>2</sup>).

Akaibel: /* Berechnung der Laufzeit für 1000 Elemente */

2016-11-28T14:59:18Z

Berechnung der Laufzeit für 1000 Elemente

← Nächstältere Version		Version vom 28. November 2016, 14:59 Uhr
Zeile 40:		Zeile 40:
	\|}		\|}

	Insgesamt braucht man also <math>1+2+...+998+999 = {999 \~~mult~~ 1000} \over {2} = 499.500</math> Vergleiche.		'''Gesamtzahl der notwendigen Vergleiche'''
			Insgesamt braucht man also <math>1+2+...+998+999 = {{999 \times 1000} \over {2}} = 499.500</math> Vergleiche.

Akaibel: Die Seite wurde neu angelegt: „=Grundidee= Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint. Stattdessen wird die '''Menge der Opera…“

2016-11-28T14:56:59Z

Die Seite wurde neu angelegt: „=Grundidee= Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint. Stattdessen wird die '''Menge der Opera…“

Neue Seite

=Grundidee=
Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint.

Stattdessen wird die '''Menge der Operationen''' abgeschätzt, die notwendig sind, um die der Algorithmus braucht. Dabei gilt folgende vereinfachende Grundannahmen:
* Die Anzahl der Operationen wird bestimmt in Abhängigkeit von der Größe des Problems, d.h. die Laufzeit ist in der Regel eine Funktion.
* In der Regel reicht es, die am häufigsten vorkommende Operation abzuschätzen - oft fallen die anderen Operationen nicht ins Gewicht.
* Jede Operation gilt als gleich "teuer".

Die Algorithmen lassen sich - gemäß ihrer Laufzeit - in verschiedene Klassen, die sogenannten [[Landau-Klassen]] einteilen.

=Vorgehensweise=
In der Regel ist es hilfreich, erst die Laufzeit für eine vorgegebene Größe des Problems (z.B. 1000) zu bestimmen.

Dann schließt man auf die Laufzeit des Problems allgemein.

=Beispiel: Insertionsort=
Bei Insertionsort wird die Ergebnisliste nach und nach aufgebaut.

Dazu wird jeweils das erste Element aus der ursprünglichen Liste genommen und gelöscht. Dann wird die Ergebnisliste von vorne bis zu der Stelle durchlaufen, an der das Element eingefügt werden muss; da wird es dann eingefügt.

==Berechnung der Laufzeit für 1000 Elemente==
Die häufigste vorkommende Operation bei Insertionsort ist der Vergleich; nur dieser wird hier abgeschätzt.

{| class="wikitable"
|+ Notwendige Vergleiche für jedes Element
! Element Nr. !! Anzahl Vergleiche beim Einfügen
|-
| 1 || 0
|-
| 2 || 1
|-
| 3 || 2
|-
| ... || ...
|-
| 999 || 998
|-
| 1000 || 999
|}

Insgesamt braucht man also <math>1+2+...+998+999 = {999 \mult 1000} \over {2} = 499.500</math> Vergleiche.