Asymptotyczne tempo wzrostu

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Ten artykuł wymaga dopracowania.
Więcej informacji co należy poprawić, być może znajdziesz na odpowiedniej stronie. W pracy nad artykułem należy korzystać z zaleceń edycyjnych. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.
Możesz także przejrzeć pełną listę stron wymagających dopracowania.

Do opisu złożoności asymptotycznej stosuje się trzy notacje:

Notacja wielkie O (porównaj: Duże O)
Notacja $Ω$ (Omega wielkie)
Notacja $Θ$ (Teta)

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

[edytuj] Notacja "Wielkie O"

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

$\begin{matrix} \forall & f(n) \leq c \cdot g(n) \\ {}^{n \geq n_0} \end{matrix}$

Zapis: $f (n) = O (g (n))$

Określenia "złożoność co najwyżej O(f(n))" i "złożoność O(f(n))" są matematycznie równoważne.

Zobacz też: Notacja dużego O.

[edytuj] Notacja "Wielkie Omega"

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

$\begin{matrix} \forall & f(n) \geq c \cdot g(n) \\ {}^{n \geq n_0} \end{matrix}$

Zapis: $f (n) = Ω(g (n))$

[edytuj] Notacja "Teta"

Mówimy, że f jest dokładnie rzędu g, gdy istnieją takie stałe $n 0 > 0$ , oraz $c 1 > 0$ i $c 2 > 0$ , że:

$\begin{matrix} \forall & c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \\ {}^{n \geq n_0} \end{matrix}$

Zapis: $f (n) = Θ(g (n))$

Można powiedzieć, że $f (n) = Θ(g (n))$ , gdy $f (n)$ jest jednocześnie rzędu $O (g (n))$ i $Ω(g (n))$ .

[edytuj] Definicje algebraiczne O, o, Ω, ω, Θ

Notacja	Definicja
$f(n) \in O(g(n))$	$\lim_{x \to \infty} \left\|\frac{f(x)}{g(x)}\right\| < \infty$
$f(n) \in o(g(n))$	$\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0$
$f(n) \in \Omega(g(n))$	$\lim_{x \to \infty} \left\|\frac{f(x)}{g(x)}\right\| > 0$
$f(n) \in \omega(g(n))$	$\lim_{x \to \infty} \frac{f(x)}{g(x)} = \infty$
$f(n) \in \Theta(g(n))$	$0 < \lim_{x \to \infty} \left\|\frac{f(x)}{g(x)}\right\| < \infty$