Asymptotyczne tempo wzrostu

Asymptotyczne tempo wzrostu – miara określająca 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 ${\displaystyle \mathrm {O} }$ (omikron; U+039F, kod HTML: Ο, Math: \Omicron) oraz jego modyfikacje, m.in. notacja ${\displaystyle \Omega }$ (omega), ${\displaystyle \Theta }$ (theta).

Notacja dużego ${\displaystyle \mathrm {O} }$ została zaproponowana po raz pierwszy w roku 1894 przez niemieckiego matematyka Paula Bachmanna(inne języki)^[1]. W późniejszych latach spopularyzował ją w swoich pracach Edmund Landau, niemiecki matematyk, stąd czasem nazywana jest notacją Landaua.

Definicje analityczne

Niech będą dane funkcje ${\displaystyle f}$ oraz ${\displaystyle g,}$ których dziedziną jest zbiór liczb naturalnych, natomiast przeciwdziedziną zbiór liczb rzeczywistych dodatnich.

Notacja „duże Ο”

Mówimy, że ${\displaystyle f}$ jest co najwyżej rzędu ${\displaystyle g,}$ gdy istnieją takie stałe ${\displaystyle n_{0}>0,}$ oraz ${\displaystyle c>0,}$ że:

${\displaystyle \forall n\geqslant n_{0}:f(n)\leqslant c\cdot g(n)}$

Zapis: ${\displaystyle f(n)\in \mathrm {O} (g(n))}$

Określenia „złożoność co najwyżej ${\displaystyle \mathrm {O} (f(n))}$” i „złożoność ${\displaystyle \mathrm {O} (f(n))}$” są matematycznie równoważne.

Wersja notacji dla zachowania się funkcji w pobliżu punktu ${\displaystyle a{:}}$

${\displaystyle f(n)\in \mathrm {O} (g(n)),}$ jeżeli istnieje takie ${\displaystyle c>0}$ i takie ${\displaystyle \delta >0,}$ że dla każdego ${\displaystyle x}$ o tej własności, że ${\displaystyle |x-a|<\delta }$ zachodzi nierówność:

${\displaystyle |f(x)|\leqslant c\cdot |g(x)|.}$

Należy zauważyć, że nie precyzuje się tu dziedziny funkcji ${\displaystyle f}$ i ${\displaystyle g}$ – zależy ona od kontekstu, w jakim występują obie funkcje.

Notacja „małe ο”

Mówimy, że ${\displaystyle f}$ jest niższego rzędu niż ${\displaystyle g,}$ gdy dla każdej stałej ${\displaystyle c>0}$ istnieje stała ${\displaystyle n_{0}>0,}$ że:

${\displaystyle \forall n\geqslant n_{0}:f(n)<c\cdot g(n)}$

Zapis: ${\displaystyle f(n)\in \mathrm {o} (g(n))}$

Notacja „Ω”

Mówimy, że ${\displaystyle f}$ jest co najmniej rzędu ${\displaystyle g,}$ gdy istnieją takie stałe ${\displaystyle n_{0}>0,}$ oraz ${\displaystyle c>0,}$ że:

${\displaystyle \forall n\geqslant n_{0}:f(n)\geqslant c\cdot g(n)}$

Zapis: ${\displaystyle f(n)\in \Omega (g(n))}$

Notacja „ω”

Mówimy, że ${\displaystyle f}$ jest wyższego rzędu niż ${\displaystyle g,}$ gdy dla każdej stałej ${\displaystyle c>0}$ istnieje stała ${\displaystyle n_{0}>0,}$ że:

${\displaystyle \forall n\geqslant n_{0}:f(n)>c\cdot g(n)}$

Zapis: ${\displaystyle f(n)\in \omega (g(n))}$

Notacja „Θ”

Mówimy, że ${\displaystyle f}$ jest dokładnie rzędu ${\displaystyle g,}$ gdy istnieją takie stałe ${\displaystyle n_{0}>0,}$ oraz ${\displaystyle c_{1}>0}$ i ${\displaystyle c_{2}>0,}$ że:

${\displaystyle \forall n\geqslant n_{0}:c_{1}\cdot g(n)\leqslant f(n)\leqslant c_{2}\cdot g(n)}$

Zapis: ${\displaystyle f(n)\in \Theta (g(n))}$

Można powiedzieć, że ${\displaystyle f(n)\in \Theta (g(n)),}$ gdy ${\displaystyle f(n)}$ jest jednocześnie rzędu ${\displaystyle \mathrm {O} (g(n))}$ i ${\displaystyle \Omega (g(n)).}$

Właściwości

Notacja dużego ${\displaystyle \mathrm {O} }$ pozwala wykonywać działania na funkcjach, na przykład:

• jeśli ${\displaystyle f(x)\in \mathrm {O} (r(x))}$ i ${\displaystyle g(x)\in \mathrm {O} (r(x)),}$ to również ${\displaystyle f(x)\pm g(x)\in \mathrm {O} (r(x)).}$
• przy założeniach jak poprzednio, ${\displaystyle f(x)\cdot g(x)\in \mathrm {O} (r^{2}(x))}$

Wygoda notacji dużego ${\displaystyle \mathrm {O} }$ widoczna jest w następującej sytuacji: jeżeli ${\displaystyle f(x)=2x^{3}-x^{2}+100x,}$ to można napisać zarówno ${\displaystyle f(x)\in \mathrm {O} (x^{3}),}$ jak i ${\displaystyle f(x)\in 2x^{3}+\mathrm {O} (x^{2}),}$ czy wreszcie ${\displaystyle f(x)\in 2x^{3}-x^{2}+\mathrm {O} (x),}$ zależnie od wymaganej dokładności oszacowań.

Napis ${\displaystyle g(x)\in f(x)+\mathrm {O} (h(x))}$ należy rozumieć jako ${\displaystyle g(x)-f(x)\in \mathrm {O} (h(x)).}$

Zależności algebraiczne Ο, ο, Ω, ω, Θ

Notacja	Warunek wystarczający
${\displaystyle f(x)\in \mathrm {O} (g(x))}$	${\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|<\infty }$
${\displaystyle f(x)\in \mathrm {o} (g(x))}$	${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0}$
${\displaystyle f(x)\in \Omega (g(x))}$	${\displaystyle \lim _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0}$
${\displaystyle f(x)\in \omega (g(x))}$	${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty }$
${\displaystyle f(x)\in \Theta (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ść:

${\displaystyle (f(n)\in \Theta (g(n))\land g(n)\in \Theta (h(n))\Rightarrow f(n)\in \Theta (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))}$

${\displaystyle (f(n)\in \Omega (g(n))\land g(n)\in \Omega (h(n))\Rightarrow f(n)\in \Omega (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))}$

${\displaystyle (f(n)\in \omega (g(n))\land g(n)\in \omega (h(n))\Rightarrow f(n)\in \omega (h(n))}$

Zwrotność:

${\displaystyle f(n)\in \Theta (f(n))}$

${\displaystyle f(n)\in \Omega (f(n))}$

${\displaystyle f(n)\in \mathrm {O} (f(n))}$

Symetria:

${\displaystyle f(n)\in \Theta (g(n))\Leftrightarrow g(n)\in \Theta (f(n))}$

Symetria transpozycyjna:

${\displaystyle f(n)\in \mathrm {O} (g(n))\Leftrightarrow g(n)\in \Omega (f(n))}$

${\displaystyle f(n)\in \mathrm {o} (g(n))\Leftrightarrow g(n)\in \omega (f(n))}$

Twierdzenie

Dla dowolnych dwóch funkcji ${\displaystyle f(n)}$ i ${\displaystyle g(n)}$ zachodzi zależność:

${\displaystyle f(n)\in \Theta (g(n))\Leftrightarrow f(n)\in \mathrm {O} (g(n))\land f(n)\in \Omega (g(n))}$^[2]

Notacje teorii liczb

Notacja Winogradowa

Zapis stosowany przez rosyjskiego matematyka, Iwana Winogradowa, utrwalił się w literaturze, szczególnie w analitycznej teorii liczb, choć w praktyce jest ona równoważna z notacją dużego „O”.

Mówimy, że ${\displaystyle f}$ jest dominowane przez ${\displaystyle g,}$ jeśli

${\displaystyle f(n)\ll g(n)\iff f(n)\in O(g(n)).}$

Analogicznie, powiemy, że ${\displaystyle g}$ jest dominowane przez ${\displaystyle f,}$ jeśli

${\displaystyle f(n)\gg g(n)\iff g(n)\in O(f(n)).}$

Notacja „${\displaystyle \asymp }$”

${\displaystyle f(n)\asymp g(n)\iff g(n)\ll f(n)\ll g(n)}$

Przykłady

• Jeżeli ${\displaystyle f(x)=1000x^{50}+2x^{2}}$ oraz ${\displaystyle g(x)=0,0000001x^{50}+665x,}$ to ${\displaystyle f(x)\in \mathrm {O} (x^{50})}$ oraz ${\displaystyle g(x)\in \mathrm {O} (x^{50}),}$ ale również ${\displaystyle g(x)\in \mathrm {O} (f(x)).}$
• Niech ${\displaystyle S(n)=1+2+\ldots +n.}$ Korzystając ze wzorów sumacyjnych: ${\displaystyle S(n)={\frac {n(n+1)}{2}}<3\cdot n^{2},}$ a zatem ${\displaystyle S(n)\in \mathrm {O} (n^{2}).}$
• Jeżeli potrzebne jest dokładniejsze oszacowanie ${\displaystyle S(n),}$ to na podstawie tego samego wzoru sumacyjnego można napisać ${\displaystyle S(n)={\frac {n^{2}}{2}}+{\frac {n}{2}}\in {\frac {n^{2}}{2}}+\mathrm {O} (n).}$
• Analogicznie można napisać, że ${\displaystyle 1^{2}+2^{2}+\ldots +n^{2}\in O(n^{3}).}$

Zastosowanie

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 ${\displaystyle f(n)={\frac {n}{1000}}}$ (funkcja liniowa ${\displaystyle \Theta (n)}$) i ${\displaystyle g(n)=\log n}$ (funkcja logarytmiczna ${\displaystyle \Theta (\log n)}$), zachodzi oszacowanie ${\displaystyle f(n)\in \omega (g(n))}$ (${\displaystyle f(n)}$ asymptotycznie rośnie szybciej niż ${\displaystyle g(n),}$ gdyż ${\displaystyle {\frac {n}{\log n}}\to \infty }$), ale dla ${\displaystyle n=10}$ wartość funkcji ${\displaystyle f}$ jest mniejsza niż funkcji ${\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).

Standardowe oszacowania

notacja	ograniczenie	rząd złożoności obliczeniowej
${\displaystyle \mathrm {O} (1)}$	funkcją stałą	złożoność stała (niezależna od rozmiaru danych wejściowych)
${\displaystyle \mathrm {O} (\log n)}$	funkcją logarytmiczną[a]	złożoność logarytmiczna
${\displaystyle \mathrm {O} (n)}$	funkcją liniową	złożoność liniowa
${\displaystyle \mathrm {O} (n\log n)}$		złożoność liniowo-logarytmiczna (lub quasi-liniowa)
${\displaystyle \mathrm {O} (n^{2})}$	funkcją kwadratową	złożoność kwadratowa
${\displaystyle \mathrm {O} (n^{k})}$	wielomianem	złożoność wielomianowa
${\displaystyle \mathrm {O} (a^{n})}$	funkcją wykładniczą	złożoność wykładnicza
${\displaystyle \mathrm {O} (n!)}$	silnią

Zobacz też

• wzrost wykładniczy
• złożoność obliczeniowa

Przypisy