Arbeitsblatt 08 - Winter PDF

Preview

Summary

Winter...

Description

Institut für Angewandte und Numerische Mathematik Dr. Mathias J. Krause M. Sc. Albert Mink M. Sc. Zoltan Veszelka

05.12.2017

Einstieg in die Informatik und Algorithmische Mathematik

Arbeitsblatt 8 Hinweis: Die Besprechung der Lösung findet am 12.12.2017 in der Übung statt.

Aufgabe 30

Komplexität

Betrachten Sie die nachfolgenden Methodendefinitionen. Jede Methode besitzt einen formalen Parameter vom Typ int, über den eine natürliche Zahl n ∈ N an die Methode übergeben werden kann. Geben Sie jeweils den asymptotischen Rechenaufwand (hier: Anzahl der Multiplikationen) der Methoden in Abhängigkeit von n als Landau-Symbol an. Mögliche Landau-Symbole sind O(1), O(log n), O(n), O(n log n), O(n2 ), O(n3 ), O(bn ), O(n!). (a)

static int methode(int n) { int s = 1; for (int i=1; i...