[Uni] Aufwandsabschätzung von Programmen

In diesem Blogpost soll es um die Aufwandsabschätzung von Programmen gehen. Die Aufwandsabschätzung ist für die Klassifizierung eines Programmes von Vorteil.

Theorie

Wozu Aufwandsabschätzung?

Wenn man schon einige Programme geschrieben hat, dann fragt man sich irgendwann, ob die Implementierung eines Algorithmus zum Lösen eines Problems auch effizient ist. Vielleicht ist man sich bewusst, dass die eigene Implementierung nicht sehr performant ist, und man begründet diese mit den “schnellen” CPUs der heutigen Zeit, sodass eine längere Wartezeit von ein paar ms kaum zu merken ist.

Der Ansatz ist zwar verständlich, jedoch ist das nicht perfekt. Mit der Aufwandsabschätzung möchte man sich von der gefühlten Laufzeit eines Algorithmus lösen (Bsp: 1GhZ CPU: 1 Sek; 100 MhZ CPU: 10 Sekunden) und genau bestimmen, für welche Eingabe n der Algorithmus welche Aufwandsklasse, also Laufzeit, hat.

Man macht den Aufwand von der Eingabe abhängig, was auch logisch ist, denn wenn ein Algorithmus mehr zu tun hat, dann braucht dieser eben auch länger.

Aufwandsklassen

Es wurden einige Aufwandsklassen erstellt, welche die Programme nach ihrem Aufwand klassifizieren sollen. Man benutzt für die obere Schranke (Aufwand wächst langsamer oder gleich schnell) der Klassen die $\mathcal{O}$ -Notation. (Worstcase)

Die Notation für die untere Schranke (Aufwand wächst gleich schnell oder schneller) ist die $\Omega$ -Notation. (Bestcase)

Für alle Algorithmen, dessen Aufwand genauso stark wächst, nutzt man die $\Theta$ -Notation. (Averagecase)

Ich werde mich hier auf die $\mathcal{O}$ -Notation beschränken. Bei dieser kann man immer nach oben hin gröber werden. Man bestimmt also den Aufwand im Worstcase.

$\mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n * \log n) < \mathcal{O}(n^c) < \mathcal{O}(c^k) < \mathcal{O}(n^k)$

Ich bringe hier mal ein kleines Beispiel, in dem wir die folgenden Funktionen nehmen:

$\begin{align*} f_1(n)&=100*n\\ f_2(n)&=5*n^2\\ f_3(n)&=0.5*n^3\\ f_4(n)&=2^n\\ \end{align*}$

Wenn man sich die Graphen nicht direkt vorstellen kann, dann kann man einen Plotter nutzen. Man könnte argumentieren, dass der Aufwand f_2 geringer als der von z.B. f_1 wäre, da bis zum Schnittpunkt die Funktionswerte von f_2 unter denen von f_1 liegen. Das ist jedoch nicht ganz richtig, da wie oben schon gesagt, wir uns für große Eingaben n interessieren.

Dann kommt man auf die Lösung, dass f_4 den größten Aufwand hat, und die anderen Funktionen langsamer wachsen. Ein weiteres Beispiel wäre f_2 mit quadratischem Aufwand, bei dem nur f_1 langsamer wächst:

$\begin{align*} \mathcal{O}(f_4)&= \{f_1,f_2,f_3,f_4\}\\ \mathcal{O}(f_2)&= \{f_1,f_2\} \end{align*}$

Welche Algorithmen werden als effizient bzw. ineffizient bezeichnet?

Diese Frage ist relativ leicht zu beantworten, denn es werden alle Algorithmen mit einem Aufwand < $\mathcal{O}(2<sup>n</sup>)$ als effizient bezeichnet. Alles was größer oder gleich dem exponientiellen Wachstum ist, gilt als ineffizient, da schon für Eingaben ab n=100 bzw. n=1000 die zeitliche Abschätzung als hoffnungslos bezeichnet wird.

Um den Aufwand korrekt zu bestimmen, benötigt man einige wichtige Rechenregeln:

$\begin{align*} f &\in \mathcal{O}(f)&(\mbox{reflexiv})\\ \mathcal{O}(\mathcal{O}(f)) &= \mathcal{O}(f)&(\mbox{transitiv})\\ \mathcal{O}(c + f) &= \mathcal{O}(f) & (\mbox{Konstanten fallen weg, da }\mathcal{O}(c) \in \mathcal{O}(f))\\ c* \mathcal{O}(f) &= \mathcal{O}(f) & (\mbox{Das gleiche, wie zuvor})\\ \mathcal{O}(f + g) &= \mathcal{O}(f) + \mathcal{O}(g)\\ \mathcal{O}(f * g) &= \mathcal{O}(f) * \mathcal{O}(g)\\ \mathcal{O}(f + g) &= \mathcal{O}(f) & (\mbox{falls } \mathcal{O}(g) \subseteq \mathcal{O}(f))\\ \end{align*}$

Zuletzt folgt noch eine Art Tabelle mit häufigen Rekurrenzgleichungen zur Berechnung des Aufwands:

$\begin{align*} A(n) &= A(n-1) + b*n^k & &\Rightarrow\mathcal{O}(n^{k+1})\\ A(n) &= c*A(n-1) + b*n^k & \mbox{mit c > 1} &\Rightarrow\mathcal{O}(c^{n})\\ A(n) &= c*A(n/d) + b*n^k & \mbox{mit c > $d^k$}&\Rightarrow\mathcal{O}(n^{\log_d c})\\ A(n) &= c*A(n/d) + b*n^k & \mbox{mit c = $d^k$}&\Rightarrow\mathcal{O}(n^{k}*\log n)\\ A(n) &= c*A(n/d) + b*n^k & \mbox{mit c < $d^k$}&\Rightarrow\mathcal{O}(n^{k})\\ \end{align*}$

Bisher sollte die Theorie ausreichen, um die Aufwandsberechnung in ihren Grundzügen zu verstehen.

Praxis

Wie immer möchte ich die oben vorgestellte Theorie mit einem / einigen Beispielen erklären.

Nehmen wir einfach eine einfache Funktion dessen Aufwand wir bestimmen möchten:

def mult(x,y):
        return x*y

Diese Funktion nimmt zwei Argumente x,y und gibt ihr Produkt zurück. Wenn man den Aufwand dieser Funktion bestimmen möchte, dann muss man den Aufwand der einzelnen Operationen wissen und kombinieren.

Bei diesem Beispiel ist die Aufwandsberechnung relativ einfach, denn:

$\begin{align*} A_{mult}(n) &= A_*\\ A_{mult}(n) &\in \mathcal{O}(1) \end{align*}$

Es gibt nur eine Operation (*), und egal was für eine große Eingabe n man nimmt, das Programm führt eben nur eine Operation durch. Deswegen ist der Aufwand dieser Funktion konstant.

Weiteres Beispiel:

def fak(num):
  if(num == 0):
      return 1
  return num*fak(num-1)

Dies soll eine Funktion sein, welche die Fakultät rekursiv berechnet.

Der Aufwand dafür kann so bestimmt werden:

$\begin{align*} A_{fak}(n) &= A_{if} + A_{*} + A_{fak}(n-1)\\ A_{fak}(n) &= A_{const} + A_{fak}(n-1)\\ \end{align*}$

Jetzt schauen wir in die Tabelle mit den Rekurrenzgleichungen und suchen die passende raus. In dem Fall ist es die erste, denn:

$\begin{align*} \mbox{1. Zeile: }&b= 1;\\ &n= 1; \\ &k= 0;\\ \mbox{Ergebnis:} & A_{fak} \in \mathcal{O}(n^{0+1}) = \mathcal{O}(n) \end{align*}$

Somit hat diese Fakultätsberechnung linearen Aufwand.

Beispiel 3:

def calc(x):
  if(x < 0):
      return 0
  if(x == 0):
      return 1
  return calc(x-1)*help(x)
  
def help(x):
  if(x == 0):
      return x*x
  return help(x-1)

Auch wenn die Funktion kaum Sinn ergibt, da die für eine Eingabe != 0 immer 0 zurückgeben wird, wollen wir trotzdem mal den Aufwand der Funktion calc bestimmen.

$\begin{align*} A_{calc}(n) &= A_{if} + A_{if} + A_* + A_{calc}(n-1) + A_{help}(n)\\ A_{calc}(n) &= A_{const} + A_{calc}(n-1) + A_{help}(n) \end{align*}$

An der Stelle kommen wir zunächst nicht weiter, da wir den Aufwand der Hilfsfunktion wissen müssen. Deswegen bestimmen wir den Aufwand bevor es mit der calc-Funktion weitergeht.

$\begin{align*} A_{help} &= A_{if} + A_* + A_{help}(n-1)\\ A_{help} &= A_{const} + A_{help}(n-1)\\ \end{align*}$

Ähnlich wie im zweiten Beispiel kommen wir hier auf linearen Aufwand.

$\begin{align*} \mbox{1. Zeile: }&b= 1;\\ &n= 1; \\ &k= 0;\\ \mbox{Ergebnis:} & A_{help} \in \mathcal{O}(n^{0+1}) = \mathcal{O}(n) \end{align*}$

Dann können wir den Aufwand von help in den Aufwand von cal einsetzen:

$\begin{align*} A_{calc}(n) &= A_{if} + A_{if} + A_* + A_{calc}(n-1) + A_{help}(n)\\ A_{calc}(n) &= A_{const} + A_{calc}(n-1) + A_{help}(n)\\ A_{calc}(n) &= A_{const} + A_{calc}(n-1) + n \end{align*}$

Und nun noch einmal in die Rekurrenzgleichungen schauen:

$\begin{align*} \mbox{1. Zeile: }&b= 1;\\ &n= 1; \\ &k= 1;\\ \mbox{Ergebnis:} & A_{calc} \in \mathcal{O}(n^{1+1}) = \mathcal{O}(n^2) \end{align*}$

Die calc Funktion hat nun also einen quadratischen Aufwand.

Fazit

Ich hoffe ich konnte die Aufwandsberechnung ein wenig klarer machen bzw. näher bringen.

Gehaxelts Blog

IT-Security & Hacking

Theorie

Wozu Aufwandsabschätzung?

Aufwandsklassen

Praxis

Fazit