Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń , w celu opisu złożoności obliczeniowej , czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu . Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.
Do opisu asymptotycznego tempa wzrostu stosuje się notację dużego
O
{\displaystyle \mathrm {O} }
omikron ; U +039F, kod HTML : Ο) oraz jej modyfikacje, m.in. notacja
Ω
{\displaystyle \Omega }
omega ),
Θ
{\displaystyle \Theta }
theta ).
Notacja dużego O została zaproponowana po raz pierwszy w roku 1894 przez niemieckiego matematyka Paula Bachmanna [1] Edmund Landau , niemiecki matematyk, stąd czasem nazywana jest notacją Landaua.
Definicje analityczne [ edytuj ] Niech będą dane funkcje
f
{\displaystyle f}
g
{\displaystyle g}
dziedziną jest zbiór liczb naturalnych , natomiast przeciwdziedziną zbiór liczb rzeczywistych dodatnich.
Notacja „duże O” [ edytuj ] Mówimy, że
f
{\displaystyle f}
jest co najwyżej rzędu
g
{\displaystyle g}
n
0
>
0
{\displaystyle n_{0}>0}
c
>
0
{\displaystyle c>0}
∀
n
⩾
n
0
:
f
(
n
)
⩽
c
⋅
g
(
n
)
{\displaystyle \forall n\geqslant n_{0}:\ f(n)\leqslant c\cdot g(n)}
Zapis:
f
(
n
)
∈
O
(
g
(
n
)
)
{\displaystyle f(n)\in \mathrm {O} (g(n))}
Określenia „złożoność co najwyżej
O
(
f
(
n
)
)
{\displaystyle \mathrm {O} (f(n))}
złożoność
O
(
f
(
n
)
)
{\displaystyle \mathrm {O} (f(n))}
są matematycznie równoważne .
Wersja notacji dla zachowania się funkcji w pobliżu punktu
a
{\displaystyle a}
f
(
n
)
∈
O
(
g
(
n
)
)
{\displaystyle f(n)\in O(g(n))}
c
>
0
{\displaystyle c>0}
δ
>
0
{\displaystyle \delta >0}
x
{\displaystyle x\;}
|
x
−
a
|
<
δ
{\displaystyle |x-a|<\delta }
|
f
(
x
)
|
⩽
c
⋅
|
g
(
x
)
|
{\displaystyle |f(x)|\leqslant c\cdot |g(x)|}
Należy zauważyć, że nie precyzuje się tu dziedziny funkcji
f
{\displaystyle f}
g
{\displaystyle g}
Notacja „małe o” [ edytuj ] Mówimy, że
f
{\displaystyle f}
jest niższego rzędu niż
g
{\displaystyle g}
c
>
0
{\displaystyle c>0}
n
0
>
0
{\displaystyle n_{0}>0}
∀
n
⩾
n
0
:
f
(
n
)
<
c
⋅
g
(
n
)
{\displaystyle \forall n\geqslant n_{0}:\ f(n)<c\cdot g(n)}
Zapis:
f
(
n
)
∈
o
(
g
(
n
)
)
{\displaystyle f(n)\in \mathrm {o} (g(n))}
Notacja „Ω” [ edytuj ] Mówimy, że
f
{\displaystyle f}
jest co najmniej rzędu
g
{\displaystyle g}
n
0
>
0
{\displaystyle n_{0}>0}
c
>
0
{\displaystyle c>0}
∀
n
⩾
n
0
:
f
(
n
)
⩾
c
⋅
g
(
n
)
{\displaystyle \forall n\geqslant n_{0}:\ f(n)\geqslant c\cdot g(n)}
Zapis:
f
(
n
)
∈
Ω
(
g
(
n
)
)
{\displaystyle f(n)\in \Omega (g(n))}
Notacja „ω” [ edytuj ] Mówimy, że
f
{\displaystyle f}
jest wyższego rzędu niż
g
{\displaystyle g}
c
>
0
{\displaystyle c>0}
n
0
>
0
{\displaystyle n_{0}>0}
∀
n
⩾
n
0
:
f
(
n
)
>
c
⋅
g
(
n
)
{\displaystyle \forall n\geqslant n_{0}:\ f(n)>c\cdot g(n)}
Zapis:
f
(
n
)
∈
ω
(
g
(
n
)
)
{\displaystyle f(n)\in \omega (g(n))}
Notacja „Θ” [ edytuj ] Mówimy, że
f
{\displaystyle f}
jest dokładnie rzędu
g
{\displaystyle g}
n
0
>
0
{\displaystyle n_{0}>0}
c
1
>
0
{\displaystyle c_{1}>0}
c
2
>
0
{\displaystyle c_{2}>0}
∀
n
⩾
n
0
:
c
1
⋅
g
(
n
)
⩽
f
(
n
)
⩽
c
2
⋅
g
(
n
)
{\displaystyle \forall n\geqslant n_{0}:\ c_{1}\cdot g(n)\leqslant f(n)\leqslant c_{2}\cdot g(n)}
Zapis:
f
(
n
)
∈
Θ
(
g
(
n
)
)
{\displaystyle f(n)\in \Theta (g(n))}
Można powiedzieć, że
f
(
n
)
∈
Θ
(
g
(
n
)
)
{\displaystyle f(n)\in \Theta (g(n))}
f
(
n
)
{\displaystyle f(n)}
O
(
g
(
n
)
)
{\displaystyle \mathrm {O} (g(n))}
Ω
(
g
(
n
)
)
{\displaystyle \Omega (g(n))}
Notacja dużego
O
{\displaystyle \mathrm {O} }
jeśli
f
(
x
)
∈
O
(
r
(
x
)
)
{\displaystyle f(x)\in O(r(x))}
g
(
x
)
∈
O
(
r
(
x
)
)
{\displaystyle g(x)\in \mathrm {O} (r(x))\;}
f
(
x
)
±
g
(
x
)
∈
O
(
r
(
x
)
)
{\displaystyle f(x)\pm g(x)\in \mathrm {O} (r(x))}
przy założeniach jak poprzednio,
f
(
x
)
⋅
g
(
x
)
∈
O
(
r
2
(
x
)
)
{\displaystyle f(x)\cdot g(x)\in \mathrm {O} (r^{2}(x))}
Wygoda notacji dużego
O
{\displaystyle \mathrm {O} }
f
(
x
)
=
2
x
3
−
x
2
+
100
x
{\displaystyle f(x)=2x^{3}-x^{2}+100x}
f
(
x
)
∈
O
(
x
3
)
{\displaystyle f(x)\in \mathrm {O} (x^{3})}
f
(
x
)
∈
2
x
3
+
O
(
x
2
)
{\displaystyle f(x)\in 2x^{3}+\mathrm {O} (x^{2})}
f
(
x
)
∈
2
x
3
−
x
2
+
O
(
x
)
{\displaystyle f(x)\in 2x^{3}-x^{2}+\mathrm {O} (x)}
Napis
g
(
x
)
∈
f
(
x
)
+
O
(
h
(
x
)
)
{\displaystyle g(x)\in f(x)+\mathrm {O} (h(x))}
g
(
x
)
−
f
(
x
)
∈
O
(
h
(
x
)
)
{\displaystyle g(x)-f(x)\in \mathrm {O} (h(x))}
Zależności algebraiczne Ο, ο, Ω, ω, Θ [ edytuj ]
Notacja
Warunek wystarczający
f
(
x
)
∈
O
(
g
(
x
)
)
{\displaystyle f(x)\in \mathrm {O} (g(x))}
lim
x
→
∞
|
f
(
x
)
g
(
x
)
|
<
∞
{\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|<\infty }
f
(
x
)
∈
o
(
g
(
x
)
)
{\displaystyle f(x)\in \mathrm {o} (g(x))}
lim
x
→
∞
f
(
x
)
g
(
x
)
=
0
{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0}
f
(
x
)
∈
Ω
(
g
(
x
)
)
{\displaystyle f(x)\in \Omega (g(x))}
lim
x
→
∞
|
f
(
x
)
g
(
x
)
|
>
0
{\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0}
f
(
x
)
∈
ω
(
g
(
x
)
)
{\displaystyle f(x)\in \omega (g(x))}
lim
x
→
∞
f
(
x
)
g
(
x
)
=
∞
{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty }
f
(
x
)
∈
Θ
(
g
(
x
)
)
{\displaystyle f(x)\in \Theta (g(x))}
0
<
lim
x
→
∞
|
f
(
x
)
g
(
x
)
|
<
∞
{\displaystyle 0<\lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|<\infty }
Trychotomia może nie wystąpić w żadnym przypadku (lecz może w przypadku niektórych funkcji i argumentów). Przechodniość, zwrotność, symetria, symetria transpozycyjna są zawsze prawdziwe tylko w przypadku wymienionych zależności funkcji asymptotycznie dodatnich[2]
Przechodniość:
(
f
(
n
)
∈
Θ
(
g
(
n
)
)
∧
g
(
n
)
∈
Θ
(
h
(
n
)
)
⇒
f
(
n
)
∈
Θ
(
h
(
n
)
)
{\displaystyle (f(n)\in \Theta (g(n))\land g(n)\in \Theta (h(n))\Rightarrow f(n)\in \Theta (h(n))}
(
f
(
n
)
∈
O
(
g
(
n
)
)
∧
g
(
n
)
∈
O
(
h
(
n
)
)
⇒
f
(
n
)
∈
O
(
h
(
n
)
)
{\displaystyle (f(n)\in \mathrm {O} (g(n))\land g(n)\in \mathrm {O} (h(n))\Rightarrow f(n)\in \mathrm {O} (h(n))}
(
f
(
n
)
∈
Ω
(
g
(
n
)
)
∧
g
(
n
)
∈
Ω
(
h
(
n
)
)
⇒
f
(
n
)
∈
Ω
(
h
(
n
)
)
{\displaystyle (f(n)\in \Omega (g(n))\land g(n)\in \Omega (h(n))\Rightarrow f(n)\in \Omega (h(n))}
(
f
(
n
)
∈
o
(
g
(
n
)
)
∧
g
(
n
)
∈
o
(
h
(
n
)
)
⇒
f
(
n
)
∈
o
(
h
(
n
)
)
{\displaystyle (f(n)\in \mathrm {o} (g(n))\land g(n)\in \mathrm {o} (h(n))\Rightarrow f(n)\in \mathrm {o} (h(n))}
(
f
(
n
)
∈
ω
(
g
(
n
)
)
∧
g
(
n
)
∈
ω
(
h
(
n
)
)
⇒
f
(
n
)
∈
ω
(
h
(
n
)
)
{\displaystyle (f(n)\in \omega (g(n))\land g(n)\in \omega (h(n))\Rightarrow f(n)\in \omega (h(n))}
Zwrotność:
f
(
n
)
∈
Θ
(
f
(
n
)
)
{\displaystyle f(n)\in \Theta (f(n))}
f
(
n
)
∈
Ω
(
f
(
n
)
)
{\displaystyle f(n)\in \Omega (f(n))}
f
(
n
)
∈
O
(
f
(
n
)
)
{\displaystyle f(n)\in \mathrm {O} (f(n))}
Symetria:
f
(
n
)
∈
Θ
(
g
(
n
)
)
⇔
g
(
n
)
∈
Θ
(
f
(
n
)
)
{\displaystyle f(n)\in \Theta (g(n))\Leftrightarrow g(n)\in \Theta (f(n))}
Symetria transpozycyjna:
f
(
n
)
∈
O
(
g
(
n
)
)
⇔
g
(
n
)
∈
Ω
(
f
(
n
)
)
{\displaystyle f(n)\in \mathrm {O} (g(n))\Leftrightarrow g(n)\in \Omega (f(n))}
f
(
n
)
∈
o
(
g
(
n
)
)
⇔
g
(
n
)
∈
ω
(
f
(
n
)
)
{\displaystyle f(n)\in \mathrm {o} (g(n))\Leftrightarrow g(n)\in \omega (f(n))}
Twierdzenie [ edytuj ] Dla dowolnych dwóch funkcji
f
(
n
)
{\displaystyle f(n)}
g
(
n
)
{\displaystyle g(n)}
f
(
n
)
∈
Θ
(
g
(
n
)
)
⇔
f
(
n
)
∈
O
(
g
(
n
)
)
∧
f
(
n
)
∈
Ω
(
g
(
n
)
)
{\displaystyle f(n)\in \Theta (g(n))\Leftrightarrow f(n)\in \mathrm {O} (g(n))\land f(n)\in \Omega (g(n))}
[2]
Jeżeli
f
(
x
)
=
1000
x
50
+
2
x
2
{\displaystyle f(x)=1000x^{50}+2x^{2}}
g
(
x
)
=
0
,
0000001
x
50
+
665
x
{\displaystyle g(x)=0,0000001x^{50}+665x}
f
(
x
)
∈
O
(
x
50
)
{\displaystyle f(x)\in \mathrm {O} (x^{50})}
g
(
x
)
∈
O
(
x
50
)
{\displaystyle g(x)\in \mathrm {O} (x^{50})}
g
(
x
)
∈
O
(
f
(
x
)
)
{\displaystyle g(x)\in \mathrm {O} (f(x))}
Niech
S
(
n
)
=
1
+
2
+
⋯
+
n
{\displaystyle S(n)=1+2+\cdots +n}
wzorów sumacyjnych :
S
(
n
)
=
n
(
n
+
1
)
2
<
3
⋅
n
2
{\displaystyle S(n)={\frac {n(n+1)}{2}}<3\cdot n^{2}}
S
(
n
)
∈
O
(
n
2
)
{\displaystyle S(n)\in O(n^{2})\,}
Jeżeli potrzebne jest dokładniejsze oszacowanie
S
(
n
)
{\displaystyle S(n)}
S
(
n
)
=
n
2
2
+
n
2
∈
n
2
2
+
O
(
n
)
{\displaystyle S(n)={\frac {n^{2}}{2}}+{\frac {n}{2}}\in {\frac {n^{2}}{2}}+\mathrm {O} (n)}
Analogicznie można napisać, że
1
2
+
2
2
+
⋯
+
n
2
∈
O
(
n
3
)
{\displaystyle 1^{2}+2^{2}+\cdots +n^{2}\in \mathrm {O} (n^{3})}
Standardowe oszacowania [ edytuj ] W zastosowaniach szczególnie często notacja
O
{\displaystyle \mathrm {O} }
f
(
x
)
∈
O
(
1
)
{\displaystyle f(x)\in \mathrm {O} (1)}
f
(
x
)
{\displaystyle f(x)\;}
ograniczona
f
(
x
)
∈
O
(
log
n
)
{\displaystyle f(x)\in \mathrm {O} (\log n)}
f
(
x
)
{\displaystyle f(x)\;}
funkcję logarytmiczną
f
(
x
)
∈
O
(
n
)
{\displaystyle f(x)\in \mathrm {O} (n)}
f
(
x
)
{\displaystyle f(x)\;}
funkcję liniową
f
(
x
)
∈
O
(
n
log
n
)
{\displaystyle f(x)\in \mathrm {O} (n\log n)}
f
(
x
)
∈
O
(
n
k
)
{\displaystyle f(x)\in \mathrm {O} (n^{k})}
f
(
x
)
{\displaystyle f(x)\;}
funkcję potęgową lub wielomian
f
(
x
)
∈
O
(
a
n
)
{\displaystyle f(x)\in \mathrm {O} (a^{n})}
f
(
x
)
{\displaystyle f(x)\;}
funkcję wykładniczą
f
(
x
)
∈
O
(
n
!
)
{\displaystyle f(x)\in \mathrm {O} (n!)}
f
(
x
)
{\displaystyle f(x)\;}
silnię
Rząd złożoności obliczeniowej [ edytuj ] W zależności od asymptotycznego tempa wzrostu, funkcje dzieli się na rzędy złożoności obliczeniowej. Najczęściej wyróżnia się:
1
{\displaystyle 1\;}
stała (stała liczba operacji niezależnie od liczby danych wejściowych)
log
n
{\displaystyle \log n\;}
logarytmiczna
n
{\displaystyle n\;}
liniowa
n
log
n
{\displaystyle n\log n\;}
liniowo-logarytmiczna (lub quasi-liniowa)
n
2
{\displaystyle n^{2}\;}
kwadratowa
n
c
{\displaystyle n^{c}\;}
wielomianowa
c
n
{\displaystyle c^{n}\;}
wykładnicza
Zastosowanie [ edytuj ] Najczęstszym zastosowaniem asymptotycznego tempa wzrostu jest szacowanie złożoności problemów obliczeniowych, w szczególności algorytmów . Oszacowanie rzędów złożoności obliczeniowej funkcji pozwala na porównywanie ilości zasobów (np. czasu, pamięci), jakich wymagają do rozwiązania problemu opisanego określoną ilością danych wejściowych. W dużym uproszczeniu można powiedzieć, że im niższy rząd złożoności obliczeniowej algorytmu, tym będzie on wydajniejszy przy coraz większym rozmiarze problemu (np. ilości danych do algorytmu).
W praktyce na efektywność algorytmu wpływa duża ilość innych czynników, w tym szczegóły realizacji. Ponadto dla małych danych wejściowych asymptotyczne tempo wzrostu może nie oddawać zachowania funkcji – np. gdy
f
(
n
)
=
n
1000
{\displaystyle f(n)={\frac {n}{1000}}}
Θ
(
n
)
{\displaystyle \Theta (n)\;}
g
(
n
)
=
log
n
{\displaystyle g(n)=\log n\;}
Θ
(
log
n
)
{\displaystyle \Theta (\log n)}
f
(
n
)
∈
ω
(
g
(
n
)
)
{\displaystyle f(n)\in \omega (g(n))}
f
(
n
)
{\displaystyle f(n)\;}
g
(
x
)
{\displaystyle g(x)\;}
[potrzebny przypis ] , ale dla
n
=
10
{\displaystyle n=10\;}
f
{\displaystyle f}
g
{\displaystyle g}
Istnieje również wiele sytuacji kiedy algorytm ma lepszą złożoność obliczeniową niż inne, ale nie stosuje się go, ponieważ jego przewaga w faktycznej implementacji jest widoczna dopiero dla gigantycznych (i kompletnie niepraktycznych) wielkości wejścia, lub ma inne wady (na przykład niestabilność numeryczną – porównaj Algorytm Strassena ). Innym powodem może być na przykład fakt, że algorytm ma lepszą złożoność czasową, ale gorszą złożoność pamięciową i vice-versa (tzw. space-time tradeoff ).
Przypisy
↑ Ronald L Graham, Donald Ervin Knuth, Oren Patashnik: Matematyka konkretna . Warszawa: Wydawnictwo Naukowe PWN, 2002, s. 489. ISBN 83-01-13906-4 . ↑ a b Thomas H. T. H. Cormen Thomas H. T. H. , Charles E. Ch. E. Leiserson Charles E. Ch. E. , Ronald L. R. L. Rivest Ronald L. R. L. , Clifford C. Stein Clifford C. i inni , Wprowadzenie do algorytmów , Krzysztof K. Diks , Adam A. Malinowski , Daria D. Roszkowska , Wojciech W. Rytter (tłum.) i inni , Wydanie VII (I w PWN), Warszawa: PWN, 2015 .
