Cryptography Reference
In-Depth Information
4.1.1 Die Ordnung von Funktionen
k
,
k
k
. Für zwei
Es sei
X
eine unbeschränkte Teilmenge des
R
∈
N
,z.B.
X
=
N
Funktionen
f
,
g
:
X
→
R
schreiben wir
f
=
O
(
g
)
, wenn es Zahlen
C
,
r
∈
R
>
0
gibt, sodass
|
f
(
x
)
| ≤
C
|
g
(
x
)
|
für alle
x
∈
X
mit
|
x
| >
r
.
Da wir nur Aussagen über
große x
machen, sprechen wir vom
asymptotischen
Verhalten
.
Das
O
soll an das Wort
Ordnung
erinnern. Es werden aber eher Sprechweisen wie
f ist O
(
)
, in Worten
f ist Groß-O von g
, benutzt.
Streng genommen ist
O
g
(
g
)
eine Menge von Funktionen und die Schreibweise
.
In der Praxis verwendet man oft Funktionen zumVergleich, die besonders
einfach
sind. So lässt man beispielsweise alle Koeffizienten weg.
Vor den ersten Beispielen führen wir noch eine übliche Notation ein. Für jede
reelle Zahl
x
bezeichne
f
=
O
(
g
)
eine etwas unpräzise, aber nützliche Abkürzung für
f
∈
O
(
g
)
x
:
=
max
{
z
∈
Z
;
z
≤
x
}
das
größte Ganze
von
x
.
Beispiel
Konstante Funktionen
X
→
R
,
x
→
c
sind in
O
(
1
)
.
x
n
∈
R
[
]
=
(
)
Jede Polynomfunktion
f
x
mit
n
deg
f
ist in
O
.
1
x
2
gilt
Für die Funktion
f
mit
f
(
x
)=
+
O
1
x
.
(
)=
(
)
(
)=
+
f
x
O
x
und
f
x
x
Dabei ist die letzte Gleichung wie folgt zu verstehen:
O
1
x
.
1
(
)
−
=
+
x
2
−
∈
f
x
x
x
Zum Nachweis untersuche man die Grenzwerte
f
(
x
)
(
(
)
−
)
lim
x
bzw.
lim
x
x
f
x
x
.
x
→
∞
→
∞
Für die Logarithmusfunktion log
a
zur Basis
a
gilt
log
x
log
a
=
=
log
a
x
O
(
log
x
)
.
In der
O
-Notation ist also die Basis des Logarithmus irrelevant.
