Asymptotyczne tempo wzrostu

Z Wikipedii

Zasugerowano, aby artykuł O małe zintegrować z tym artykułem lub sekcją. (dyskusja)

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 (zwaną też notacją Landaua od nazwiska niemieckiego teoretyka liczb Edmunda Landaua, który ją spopularyzował), oraz jej modyfikacje, m.in. notacja $Ω$ (duża omega), $Θ$ (theta).

Spis treści

1 Definicje analityczne
2 Zależności algebraiczne O, o, Ω, ω, Θ
3 Przykłady
- 3.1 Standardowe oszacowania
4 Rząd złożoności obliczeniowej
5 Zastosowanie
6 Zobacz też

[edytuj] Definicje analityczne

Zasugerowano, aby sekcja [[:Asymptotyczne tempo wzrostu#Zależności algebraiczne O, o, Ω, ω, Θ|Zależności algebraiczne O, o, Ω, ω, Θ]] z artykułu Asymptotyczne tempo wzrostu została zintegrowana z tym artykułem lub sekcją. (dyskusja)

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 "duże 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.

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

$f(n)=O(g(n)) \,$ , jeżeli istnieje takie $c>0\,$ i takie $n_0 > 0\,$ , że dla dowolnych $x\,$ takich, że $|x-a|<\delta\,$ zachodzi nierówność

$|f(x)| \leq c \cdot |g(x)|$ .

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

[edytuj] Notacja "małe o"

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

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

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

[edytuj] Notacja "Ω"

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 "ω"

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

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

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

[edytuj] Notacja "Θ"

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] Uwagi

Znak "=" nie oznacza tutaj równości, jest on zdefiniowany przez podane wyżej określenia. Notacja dużego O pozwala wykonywać działania na funkcjach, na przykład:

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

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

Napis $g(x) = f(x)+O(h(x))\,$ należy rozumieć jako $g(x)-f(x) = O(h(x))\,$ .

[edytuj] Zależności algebraiczne O, o, Ω, ω, Θ

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi.
Należy w nim poprawić: ta tabela jest troszkę myląca - kolumna określana jako definicja NIE daje definicji ale warunki wystarczające tylko (granice w tej kolumnie nie muszą istnieć a warunki po lewej będą spełnione i tak) O co więc tu chodzi? I po co?.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdziesz na stronie dyskusji tego artykułu.
Po naprawieniu wszystkich błędów można usunąć tę wiadomość.

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$

[edytuj] Przykłady

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

[edytuj] Standardowe oszacowania

W zastosowaniach szczególnie często notacja O-duże pojawia się w następujących sytuacjach:

$f(x)=O(1)\,$ – funkcja $f (x)$ jest ograniczona
$f(x)=O(\log n)\,$ – funkcja $f (x)$ jest ograniczona przez funkcję logarytmiczną
$f(x)=O(n)\,$ – funkcja $f (x)$ jest ograniczona przez funkcję liniową
$f(x)=O(n \log n)\,$
$f(x)=O(n^k)\,$ – funkcja $f (x)$ jest ograniczona przez funkcję potęgową lub wielomian
$f(x)=O(a^n)\,$ – funkcja $f (x)$ jest ograniczona przez funkcję wykładniczą
$f(x)=O(n!)\,$ – funkcja $f (x)$ jest ograniczona przez silnię

[edytuj] Rząd złożoności obliczeniowej

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$	stała
$l o g 2 n$	logarytmiczna
$n$	liniowa
$n l o g 2 n$	liniowo-logarytmiczna (lub quasi-liniowa)
$n 2$	kwadratowa
$n c$	wielomianowa
$c n$	wykładnicza

[edytuj] 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.

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

[edytuj] Zobacz też

We provide Linux to the World