Informatik 12 4.1 Laufzeiten von Algorithmen

 Inhalt des Kurses    
0. Startseite   4.1 Laufzeiten von Algorithmen
1. Formale Sprachen     4.2 Grenzen der Berechenbarkeit
2. Kommunikation und Synchronisation von Prozessen  
3. Funktionsweise eines Rechners  
4. Grenzen der Berechenbarkeit    
   
   
   
Zurück zur Seite des Werner-von-Siemens-Gymnasiums Regensburg    
     
         

4.1 Laufzeiten von Algorithmen

Die grundlegenden Anweisungen einer Programmiersprache, wie das Ausführen einfacher arithmetischer Operationen, die Wertzuweisung von Attributen oder das Erzeugen neuer Objekte benötigen nur einige Nanosekunden.
Deshalb scheinen viele Programme in Echtzeit abzulaufen.

Es gibt aber auch Programme, die wesentlich mehr Operationen ausführen müssen, wie z.B. die Suche nach Elementen, das Sortieren von Elementen oder die Suche kürzester Wege in gewichteten Graphen.

Deshalb haben Überlegungen zum Laufzeitverhalten von Algorithmen in der Softwareentwicklung große Bedeutung.

 

Messen von Laufzeiten:

Mit der folgenden Methode kann man die Laufzeit einer Methode in Nanosekunden bestimmen:

public long laufzeitTesten(){
 
 long startNanoTime; 
 startNanoTime = System.nanoTime();
 
 //Hier muss die zu testende Methode aufgerufen werden. 
 
 
 return System.nanoTime() - startNanoTime;
}
 

Messfehler bei dieser Methode:

 

Qualitative Laufzeitbestimmung durch Zählen der Schritte:

Man verwaltet ein Attribut das die auszuführenden Schritte zählt und erhöht den Attributwert nach jeder Anweisung im Programm um 1. Auf diese Weise erhält man eine rechnerunabhängige Aussage über die das Laufzeitverhalten.

public class Schrittzaehlung{

   public void ggTBerechnen(int a, int b){
     int i; //Anzahl der Schritte
     i = 0;
     i++; 
     while(a!=b){
       i++; 
       if(a>=b){
         i++; 
         a = a-b;
       }
       else{
         i++; 
         b = b-a;
       }
     }
     i++; 
     System.out.println("Der ggT ist "+a);
     System.out.println("Zur Berechnung waren "+i+" Schritte erforderlich"); 
   }
}


Übung

Laufzeiten bestimmen (BlueJ)

Teste das Programm für verschiedene Methoden.


 

Die Laufzeit eines Programms ist natürlich auch von den Eingabeparametern abhängig.

Führt man eine Messreihe durch, kann man die Ergebnisse zum Beispiel mit Hilfe einer Tabellenkalkulation graphisch darstellen.

Für die rekursive Methode fibo(int n) zur Bestimmung der n-ten Fibonaccizahl (Quelltext) erhält man folgendes Laufzeitverhalten :

Fibonacci

Aufgrund der nicht linearen Rekursion (jeder rekursive Aufruf hat zwei weitere Aufrufe zur Folge) steigt die Laufzeit mit zunehmenden n stark an.

 

Übung

Schreibe eine Methode, mit der man so eine Messung der Laufzeit für die Fibonaccizahlen durchführen kann und werte die Ergebnisse in einer Tabelle aus.

Schreibe auch ein Programm, das die Anzahl der Schritte bei der Berechnung der Fibonaccizahlen ausgibt.

ExcelTabelle (auch als Vorlage für weitere Messungen)
Lösung(BlueJ)
ExcelTabelle(Lösung)

Wie kann man das exponentielle Laufzeitverhalten einfach nachweisen?

Lösung

 


Übung

Schreibe eine Methode, die die Binomialkoeffizienten B(n;k) rekursiv berechnet und untersuche das Laufzeitverhalten in Abhängigkeit von n.

Für die Binomialkoeffizienten gilt:

Formel Binomialkoeff.1

Formel Binomialkoeff.2

 

Lösungsvorschlag (BlueJ)
Lösungsvorschlag (Excel)

 


Übung

Suche in Liste und Baum (Buch S.138, Aufgabe 4)

Suche in Liste und Baum (BlueJ)

(Hinweis: Das gibt die Ergebnisse vom Typ float mit Punkt als Dezimalkomma aus. Dies wird evtl. vom Tabellenkalkulationsprogramm nicht als Zahl erkannt. In diesem Fall ändert man den Ausgabetyp besser auf integer.)

Ergebnis (Liste)
Ergebnis (Baum)

 


Übung

Wegsuche in Graphen (Buch S.138, Aufgabe 3)

Routenplaner - Wegsuche in Graphen (BlueJ)

 

Ergebnis (Brute Force)
Ergebnis (Dijkstra)

 

Brute Force Methode bei der Wegsuche in einem Graphen:

  • Man ermittelt alle zyklenfreien Wege im Graphen vom Start- zum Zielknoten.
  • Aus dieser Menge bestimmt man den Weg mit der kürzesten Weglänge.

Beim Verschlüsseln von Texten, achtet man darauf, dass eine Entschlüsselung mit Hilfe des Brute Force Verfahrens aufgrund eines hohen Laufzeitaufwands nicht realisierbar ist.


Die Landau-Notation für das Laufzeitverhalten:

O(an): exponentielles Laufzeitverhalten (Bsp.: Fibonacci-rekursiv, Brute Force bei Graphen)

O(n2): quadratisches Laufzeitverhalten (Bsp.: Bubblesort oder Insertionsort Algorithmus)

O(n*log n): super lineares Laufzeitverhalten (Bsp.: Mergesort Algorithmus)

O(n): lineares Laufzeitverhalten (Bsp.: Suchen in einer Liste)

O(log n): logarithmisches Laufzeitverhalten (Bsp.: Suchen in einem Baum)

O(p(n)): polynomiales Laufzeitverhalten. p(n) steht für eine Polynomfunktion (d.h. ganzrationale Funktion)

Die Schreibweise O(g(n)) beschreibt dabei eine so genannte Komplexitätsklasse. Man sagt, ein Algorithmus hat die Komplexität O(f(n)), wenn die Funktion f(n), die dessen Laufzeitverhalten für große n beschreibt zu dieser Klasse gehört.


Übung

Laufzeitverhalten verschiedener Sortieralgorithmen

(Buch S. 139, Aufgabe 5)

VisualSort

Untersuche das Laufzeitverhalten der Algorithmen und untersuche auch best case - und worst case - Vorsortierungen.

Eine gute Erläuterung und Visualisierung von Sortieralgorithmen findet man auf den Seiten von MathePrisma.

MathePrisma - Sortieralgorithmen

 

Zusammenfassung

 


Übung

Passwörter mit Brute Force knacken

(Buch S. 140, Aufgabe 8)

Passwort

 


Übung

Übungsaufgaben
Lösungsvorschlag (aktualisiert)
Selection Sort
Maximumbestimmung