a)Die Algorithmen A1 bis A5 benötigen für ihre Ausführung si (i∈{1,....,5}) Schritte. Die Anzahl der Schritte si
kann dabei von der Größe n der Eingabe abhängig sein und sei gegeben durch:
s1 = 23 + 5
s2 = 6 log n + 17c - log n
s3 = n0 + n1 + n2 + n3 + n4
s4 = 2 log n + 4n
s5 = n3 + 35 + 3n
Geben Sie für jeden Algorithmus die Zeitkomplexität mithilfe der O-Notation an.
b)
Gegeben sei folgender Codeausschnitt. Der Parameter n sei eine natürliche Zahl.
public void calc ( i n t n ) {
int e = 1 ;
if ( n < 1) {
System.out.println( 0 ) ;
}else {
while ( n > 1) {
e *= n ;
n--;
}
System.out.println( e ) ;
}
}
Berechnen Sie die Komplexität des Algorithmus unter Zuhilfenahme der O-Notation.
c)
Gegeben sei folgender rekursive Algorithmus zur Berechnung von Fibonacci-Zahlen. Die Methode gibt für ein n
die Fibonacci-Zahl fn zurück.
public long fibonacci (int n ) {
if ( n < 2) {
return 1 ;
} else{
return fibonacci ( n - 1) + fibonacci ( n - 2 ) ;
}
}
Ermitteln Sie die Komplexitätsklasse des Algorithmus.
d)
Gegeben sei folgender Algorithmus zur Matrizen-Multiplikation. Die Methode nimmt zwei quadratische Matrizen
entgegen und multipliziert diese. Die Variable n entspricht dabei der Anzahl an Spalten bzw. Zeilen beider
Matrizen.
public int [ ] [ ] matrizenMultiplikation ( int [ ] [ ] a , int [ ] [ ] b ) {
int n = a.length ;
int [ ] [ ] c = new int [ n ] [ ] ;
for ( int i = 0 ; i < n ; i ++) {
c [ i ] = new int [ n ] ;
for ( int j = 0 ; j < n ; j ++) {
for ( int k = 0 ; k < n ; k++) {
c [ i ] [ j ] = c [ i ] [ j ] + a [ i ] [ k ] * b [ k ] [ j ] ;
}
}
}
return c;
}
Berechnen Sie die Komplexität des Algorithmus mittels O-Notation. Vergleichen Sie den Algorithmus zur Matrizen-
Multiplikation mit dem Algorithmus zum Berechnen der Fibonacci-Zahlen (Teilaufgabe c)) für große n.
