| GEHNIO |
|
|
> Home > Algorithmen > Datenstrukturen > Probleme > Highlights > Themen > Mindmaps > Aufgaben > Programmierung > Facharbeit > Abitur > Projekte > Informatik-AG > News > Impressum |
Eingabegröße: z.B. bei Suchalgorithmen => Größe des Suchraums Hier: Suche in einer Folge von n Zahlen =>Eingabegröße n Elementarschritte: einfache Anweisungen oder Zuweisungen, einfache Berechnungen (Addieren, Subtrahieren, Multiplizieren, Dividieren), Vergleiche (If...Then), Festlegung eines Kostenmaßes: Jeder Elementarschritt "kostet" Zeit. Deshalb wird jedem Elementarschritt eine Zeiteinheit zugeordnet. (Im Beispiel mit (1) markiert!) Beispiel:
Procedure minimumsuche; (1) = eine Zeiteinheit var i : integer; (1)minimum : integer; (1) position : integer; (1) begin (1) minimum :=zahlenfolge[1]; {vorläufiges Minimum} (1) position := 1; (1) for i:=1 to n do n-mal begin (1) if zahlenfolge[i] < minimum (1) then (1) begin (1) minimum := zahlenfolge[i]; (1) position := i; (1) end; (1) end;{of for} writeln (‘Das Minimum beträgt ‘,minimum,‘ und steht an Position ‘,position,‘.‘); (1) end; {procedure Minimumsuche} (1) Zeiteinheiten summinieren: Programmkopf + Deklaration: 4 Zeiteinheiten Vor der Schleife: 3 Zeiteinheiten Schleife: n * 7 Zeiteinheiten Nach der Schleife: 2 Zeiteinheiten Zusammen: 4+3+7*n+2 Zeiteinheiten Zusammenfassen: 7*n+9 Zeiteinheiten Laufzeitfunktion T(n) in Abhängigkeit von der Größe der Eingabe n T(n) = 7*n+9 Dieser Algorithmus hat die Ordnung n, d.h. sein Laufzeitverhalten ist proportional zur Größe der Eingabe n. (Vergleiche O-Kalkül): T(n)=O(n)!
Zusammengestellt von: Adrian Scharla, 17.12.2001 Unsere Materialsammlung wird ständig ergänzt. Bitte besuchen Sie die Seite später noch einmal!
|
| © 2001 Gesamtschule Duisburg-Hamborn/Neumühl. |