Θ
{\displaystyle \Theta }
[ Bearbeiten ] Die exakte Ordnung
Θ
{\displaystyle \Theta }
Θ
(
f
(
n
)
)
=
{
g
:
N
→
N
|
∃
c
1
∈
R
>
0
,
∃
c
2
∈
R
>
0
,
∃
n
o
∈
N
∀
n
≥
n
0
:
c
1
⋅
f
(
n
)
≥
g
(
n
)
≥
c
2
⋅
f
(
n
)
}
{\displaystyle \Theta (f(n))=\{g:\mathbb {N} \to \mathbb {N} |\exists c_{1}\in \mathbb {R} ^{>0},\exists c_{2}\in \mathbb {R} ^{>0},\exists n_{o}\in \mathbb {N} \ \forall n\geq n_{0}:c_{1}\cdot f(n)\geq g(n)\geq c_{2}\cdot f(n)\}}
Oder etwas kompakter:
Θ
(
f
(
n
)
)
=
O
(
f
(
n
)
)
⋂
Ω
(
f
(
n
)
)
{\displaystyle \Theta (f(n))=O(f(n))\bigcap \Omega (f(n))}
Anschaulich formuliert bedeutet das, dass
Θ
{\displaystyle \Theta }
Zu zeigen:
Θ
(
f
(
n
)
)
⊆
O
(
f
(
n
)
)
∩
Ω
(
f
(
n
)
)
u
n
d
Θ
(
f
(
n
)
)
⊇
O
(
f
(
n
)
)
∩
Ω
(
f
(
n
)
)
{\displaystyle \Theta (f(n))\subseteq O(f(n))\cap \Omega (f(n))~und~\Theta (f(n))\supseteq O(f(n))\cap \Omega (f(n))}
Θ
(
f
(
n
)
)
⊆
O
(
f
(
n
)
)
∩
Ω
(
f
(
n
)
)
:
{\displaystyle \Theta (f(n))\subseteq O(f(n))\cap \Omega (f(n)):}
Zeige
g
(
n
)
∈
Θ
(
f
(
n
)
)
⇒
g
(
n
)
∈
O
(
f
(
n
)
)
∩
Ω
(
f
(
n
)
)
.
{\displaystyle g(n)\in \Theta (f(n))\Rightarrow g(n)\in O(f(n))\cap \Omega (f(n)).}
g
(
n
)
∈
Θ
(
f
(
n
)
)
⇒
∃
c
1
,
c
2
,
n
0
:
∀
n
≥
n
0
:
c
1
f
(
n
)
≥
g
(
n
)
≥
c
2
f
(
n
)
{\displaystyle g(n)\in \Theta (f(n))\Rightarrow \exists c_{1},c_{2},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)\geq c_{2}f(n)}
⇒
∃
c
1
,
n
0
:
∀
n
≥
n
0
:
c
1
f
(
n
)
≥
g
(
n
)
u
n
d
∃
c
2
,
n
0
:
∀
n
≥
n
0
:
c
1
f
(
n
)
≥
g
(
n
)
≥
c
2
f
(
n
)
{\displaystyle \Rightarrow \exists c_{1},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)~und~\exists c_{2},n_{0}:\forall n\geq n_{0}:c_{1}f(n)\geq g(n)\geq c_{2}f(n)}
⇒
g
(
n
)
∈
O
(
f
(
n
)
)
u
n
d
g
(
n
)
∈
Ω
(
f
(
n
)
)
{\displaystyle \Rightarrow g(n)\in O(f(n))~und~g(n)\in \Omega (f(n))}
⇒
g
(
n
)
∈
O
(
f
(
n
)
)
∩
Ω
(
f
(
n
)
)
{\displaystyle \Rightarrow g(n)\in O(f(n))\cap \Omega (f(n))}
Wir stellen uns die Frage, ob
n
2
∈
O
(
n
3
)
{\displaystyle n^{2}\in O(n^{3})}
n
3
{\displaystyle n^{3}}
n
2
{\displaystyle n^{2}}
n
0
=
1
,
c
=
1
{\displaystyle n_{0}=1,c=1}
⇒
n
2
≤
n
3
{\displaystyle \Rightarrow n^{2}\leq n^{3}}
⇒
1
≤
n
für
n
≥
1
{\displaystyle \Rightarrow 1\leq n\ {\text{für}}\ n\geq 1}
Wir stellen uns die Frage, ob
n
3
∈
O
(
n
2
)
{\displaystyle n^{3}\in O(n^{2})}
n
2
{\displaystyle n^{2}}
n
3
{\displaystyle n^{3}}
∃
c
,
n
0
∈
N
:
n
3
≤
c
⋅
n
2
,
für alle
n
>
n
0
{\displaystyle \exists c,n_{0}\in \mathbb {N} :n^{3}\leq c\cdot n^{2},{\text{für alle }}n>n_{0}}
n
3
≤
c
⋅
n
2
,
für alle
n
>
n
0
{\displaystyle n^{3}\leq c\cdot n^{2},{\text{für alle }}n>n_{0}}
⇒
n
≤
c
,
für alle
n
>
n
0
{\displaystyle \Rightarrow n\leq c,{\text{für alle }}n>n_{0}}
Wähle
n
=
c
+
n
0
⇒
c
+
n
0
≤
c
{\displaystyle n=c+n_{0}\Rightarrow c+n_{0}\leq c}
