| Author |
Message |
rgerhards
|
|
Post subject: Landau Symbole (u. a. "big O")
 Posted: Oct 15, 2008 - 03:46 PM
|
|
Joined: Sep 25, 2006
Posts: 688
Status: Offline
|
|
Die Landau-Symbole haben in der Informatik eine wichtige Bedeutung. Sie werden beispielsweise zur Abschätzung der Laufzeit von Algorithmen oder auch der Kosten von Schaltungen verwendet.
Ein guter Artikel findet sich bei Wikipedia: http://de.wikipedia.org/wiki/Landau_Symbole
Examplarisch sei hier ein Beispiel (aus dem Kurs-Skript) gezeigt:
Das sagt folgendes: wenn Du Dir  plotten lässt und  , dann wirst Du feststellen, dass die erste Funktion nicht wesentlich schneller wächst als die zweite. Das sieht so aus:
Genau genommen wächst sie also sogar langsammer, ist also  ("little o"), was aber im Skript nicht eingeführt wurde.
In der Praxis wird meist anstelle von
die Schreibweise mit Gleichheitszeichen verwendet:
Dies ist zwar üblich, aber mathematisch nicht korrekt. Insbesondere darf man sich dadurch nicht verleiten lassen, mit zwei solcher Landau-Symbole zu rechnen. |
|
|
| |
|
|
|
 |
|
|
|
|
Home Page 
Administration 
Logout 
Web Links 
FAQ
Search
Register
Log in to check your private messages
Log in
Maximize
::