Tilman
160 lines
6.0 KiB
PHP
160 lines
6.0 KiB
PHP
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
|
|
<link rel="stylesheet" type="text/css" media="all" href="stylesheet.css">
|
|
<title>Laufzeit und O-Notation</title>
|
|
</head>
|
|
<body>
|
|
<span id="menu"><a href="index.php">zurück zur Liste</a></span>
|
|
|
|
<div id="buttons">
|
|
<form action="edit.php" method="POST">
|
|
<input type="hidden" name="filename" value="<?php echo $_SERVER['SCRIPT_FILENAME']?>">
|
|
<p>
|
|
<input type="submit" value="Seite bearbeiten">
|
|
</p>
|
|
</form>
|
|
</div>
|
|
|
|
<h1>O-Notation, Laufzeiten</h1>
|
|
|
|
<h3>Laufzeit</h3>
|
|
Man kann den Zeitaufwand von Algorithmen nicht eindeutig bestimmen. Viel zu viele Faktoren (Hardware, parallel laufende Programme, Eingabereihenfolge, ...) spielen eine Rolle, so dass man mit normalen Mitteln niemals eine genaue und allgemeine Aussgae über die benötigte Zeit machen kann.<br>
|
|
Es werden nun nicht mehr die benötigten Zeiten, sondern die benötigten "greifbaren" Schritte bei einer bestimmten Eingabelänge n beschrieben.<br>
|
|
Somit können Programme in Klassen (konstant, logarithmisch, lineas, polynomial, exponentiell, u.a.) eingeteilt werden.<br><br>
|
|
|
|
<h3>O-Notation</h3>
|
|
Möchten wir nun wissen, ob eine Laufzeit in eine Klasse gehört, so müssen wir ihr asymptotisches Wachstum beobachten.<br>
|
|
Es gibt ein n<sub>0</sub> ≠ ∞, ab dem das Wachstumsverhalten vergleichbar ist mit der repräsentierenden Funktion der Klasse.<br><br>
|
|
Wir können nun die Laufzeit folgendermaßen einteilen:
|
|
<table>
|
|
<tr>
|
|
<td><b>Worst Case</b></td>
|
|
<td>
|
|
<b>f(n) = Ο(g(n))</b><br>
|
|
∃n<sub>0</sub> ∈ N ∧ c > 0, ∀n ≥ n<sub>0</sub>: |f(n)| ≤ c * g(n)
|
|
</td>
|
|
<td><b>lim<sub>n→∞</sub> f(n)/g(n) = 0 oder c</b></td>
|
|
</tr>
|
|
<tr>
|
|
<td><b>Best Case</b></td>
|
|
<td>
|
|
<b>f(n) = Ω(g(n))</b> <i>Omega</i><br>
|
|
∃n<sub>0</sub> ∈ N ∧ c > 0, ∀n ≥ n<sub>0</sub>: |f(n)| ≥ c * g(n)
|
|
</td>
|
|
<td><b>lim<sub>n→∞</sub> f(n)/g(n) → ∞ oder c</b></td>
|
|
</tr>
|
|
<tr>
|
|
<td><b>Best Case und Worst Case</b></td>
|
|
<td>
|
|
<b>f(n) = Θ(g(n))</b> <i>Theta</i><br>
|
|
∃n<sub>0</sub> ∈ N ∧ c > 0, ∀n ≥ n<sub>0</sub>: f(n) = O(g(n)) ∧ f(n) = Ω(g(n))
|
|
</td>
|
|
<td><b>lim<sub>n→∞</sub> f(n)/g(n) = c</b></td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
|
|
Die O-Notation ist eine Abschätzung der Laufzeit bei unendlich großen Eingaben. Da jedoch keine Eingabe unendlich ist, sollte man bei der Wahl von Algorithmen, die realistische Eingabelänge einbeziehen.<br>
|
|
<table>
|
|
<tr>
|
|
<td>Beispiel: </td>
|
|
<td>f(n) = 10<sup>20</sup>n</td>
|
|
<td>= O(n)</td>
|
|
</tr>
|
|
<tr>
|
|
<td></td>
|
|
<td>g(n) = 10<sup>-20</sup>n<sup>2</sup></td>
|
|
<td>= O(n<sup>2</sup>)</td>
|
|
</tr>
|
|
</table>
|
|
Obwohl O(n) < O(n<sup>2</sup>), ist f(n) > g(n) bei kleinen n.<br><br>
|
|
|
|
<h3>Anwendung</h3>
|
|
Es gibt folgenden Regeln zur Bestimmung der Klasse:
|
|
<table>
|
|
<tr>
|
|
<td><b>Addition</b></td>
|
|
<td>f(n) = n + 3</td>
|
|
<td>⇒ f(n) = Θ(n)</td>
|
|
<td>Konstante Summanden werden vernachlässigt</td>
|
|
</tr>
|
|
<tr>
|
|
<td></td>
|
|
<td>f(n) = n<sup>2</sup> + 3n</td>
|
|
<td>⇒ f(n) = Θ(n<sup>2</sup>)</td>
|
|
<td>Es zählt der Summand mit dem stärkeren Wachstum</td>
|
|
</tr>
|
|
<tr>
|
|
<td><b>Multipikation</b></td>
|
|
<td>f(n) = 3n</td>
|
|
<td>⇒ f(n) = Θ(n)</td>
|
|
<td>Konstante Faktoren werden vernachlässigt</td>
|
|
</tr>
|
|
<tr>
|
|
<td></td>
|
|
<td>f(n) = n<sup>2</sup> * 3n</td>
|
|
<td>⇒ f(n) = Θ(n<sup>3</sup>)</td>
|
|
<td>Es zählt die Summe der Exponenten</td>
|
|
</tr>
|
|
</table>
|
|
<br>
|
|
|
|
<b>Wachstum im Vergleich:</b> 1 < log n < √n < n < n(log n)<sup>2</sup> < n<sup>2</sup> < n<sup>a</sup> < a<sup>n</sup>
|
|
<br><br>
|
|
|
|
<b>Umformen der Basen von Logerithmen:</b> log<sub>c</sub>b = log<sub>a</sub>b / log<sub>a</sub>c
|
|
|
|
<br><br>
|
|
<hr>
|
|
<i><font size="+1">O - Notation</i></font><br><br>
|
|
|
|
<b>Definition</b>: f(n) und g(n) seien Funktionen von den natürlichen zu den reellen Zahlen.<br>
|
|
<font face="Times New Roman">
|
|
f(n) = Ο(g(n)) ⇔ ∃n<sub>0</sub> ∈ N ∧ c > 0, ∀n ≥ n<sub>0</sub>: |f(n)| ≤ c * g(n)<br>
|
|
f(n) = Ω(g(n)) ⇔ ∃n<sub>0</sub> ∈ N ∧ c > 0, ∀n ≥ n<sub>0</sub>: |f(n)| ≥ c * g(n)<br>
|
|
f(n) = Θ(g(n)) ⇔ ∃n<sub>0</sub> ∈ N ∧ c > 0, ∀n ≥ n<sub>0</sub>: f(n) = O(g(n)) ∧ f(n) = Ω(f(n))
|
|
</font>
|
|
<br>
|
|
<br>
|
|
|
|
<i><font size="+1">Wichtige Laufzeiten</i></font><br>
|
|
<ul>
|
|
<ol>Tiefensuche O(V+E)</ol>
|
|
<ol>Breitensuche O(V+E)</ol>
|
|
<ol>Dijktra O(V+E)</ol>
|
|
</ul>
|
|
|
|
<table border=0 width="50%">
|
|
<tr align="center">
|
|
<td></td> <td><b>best case</b></td> <td><b>middle case</b></td> <td><b>worst case</b></td>
|
|
</tr>
|
|
|
|
<tr align="center">
|
|
<td><b>Prim</b></td> <td>O(E)</td> <td>- - -</td> <td>O(V<sup>2</sup>)</td>
|
|
</tr>
|
|
|
|
<tr align="center">
|
|
<td><b>Quicksort</b></td> <td>O(n logn)</td> <td>O(n logn)</td> <td>O(n<sup>2</sup>)</td>
|
|
</tr>
|
|
|
|
<tr align="center">
|
|
<td><b>Bubblesort, Insertsort</b></td> <td>O(n<sup>2</sup>)</td> <td>O(n<sup>2</sup>)</td> <td>O(n<sup>2</sup>)</td>
|
|
</tr>
|
|
|
|
<tr align="center">
|
|
<td><b>Mergesort</b></td> <td>O(n logn)</td> <td>O(n logn)</td> <td>O(n logn)</td>
|
|
</tr>
|
|
|
|
</table>
|
|
|
|
|
|
<h2>Links</h2>
|
|
<a href="http://www.vameo.de/uni/tutorium/o-notation01.pdf">Merkblatt der O-Notation von Augustin</a><br>
|
|
<a href="http://www.sortieralgorithmen.de/mathematics.htm">O-Notation: Definition auf der Sortieralgorithmen-Seite</a><br>
|
|
<a href"=http://www.chemieonline.de/forum/showthread.php?p=196069#post196069">Laufzeit Fibonacci</a><br>
|
|
<a href="http://www.fh-wedel.de/~si/seminare/ws03/Ausarbeitung/7.effizienz/effizienz03.html#u3">Laufzeit reverse</a>
|
|
|
|
</body>
|
|
</html> |