Analiza algorytmu to sposób określenia zasobów, które są potrzebne w celu wykonania algorytmu: ilości czasu i miejsca w pamięci, szerokości pasma lub liczby układów logicznych.

W analizie algorytmu czas działania algorytmu spełnia ważną rolę, ponieważ niektóre proste problemy mogą powodować niezwykle długie obliczenia.

W analizie tej rozważa się przypadek najdłuższego czasu działania dla każdych danych wejściowych określonego rozmiaru oraz przypadek średniego czasu oczekiwania na działania danego algorytmu przy założeniu, iż wszystkie dane wejściowe określonego rozmiaru są jednakowo prawdopodobne.

Algorytm – w matematyce oraz informatyce skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić.

Od czego zależy czas wykonywania

od danych wejściowych (ciąg posortowany jest łatwiejszy do posortowania);
od wielkości strumienia wejściowego (ciąg krótszy jest łatwiejszy do posortowania);

Zwykle szukamy górnych granic czasu działania, żeby mieć gwarancję nieprzekroczenia go.

Rodzaje analizy

Najgorszy przypadek (zwykle): $T(n)=$ maksymalny czas działania algorytmu na danych wielkości n;
Średni przypadek (czasami): Oczekiwany czas działania przy każdych danych (wymaga założeń co do statystycznego rozłożenia danych);
Najlepszy przypadek (fałszywa analiza): Pokazuje, że nawet wolny algorytm pracuje szybko dla pewnych danych.

Notacja asymptotyczna

Osobny artykuł: asymptotyczne tempo wzrostu.

ignoruje stałe zależne od komputera (dzięki temu analiza jest uniwersalna, uzyskujemy te same wyniki niezależnie od maszyny);

zwraca uwagę na wzrost funkcji $T(n) \to \infty$

Notacja O (górna granica)

$O(g(n))= \{ f(n):$ istnieją stałe $c>0, n_{0}>0$ takie, że $0 \leqslant f(n) \leqslant cg(n)$ dla wszystkich $n \geqslant n_{0} \}$

Przykład: $2n^{2}=O(n^{3}), gdzie (c=1, n_{0}=2)$
Zwróć uwagę, że $n^{2} , n^{3}$ to funkcje, nie wartości. Ponadto równość jest "w jedną stronę"!
(Dokładniej operując na zbiorach powinno się pisać $2n^{2} \in O(n^{3})$ , więc, np. $O(n^{2})$ jest zbiorem funkcji i we wzorach traktuje się ten zbiór jako anonimową funkcję $h(n) \in O(n^{2}$ ).

Notacja $\Omega$ (ograniczenie dolne)

$\Omega (g(n))= \{ f(n):$ istnieją stałe $c>0, n_{0}>0$ takie, że $0 \leqslant cg(n) \leqslant f(n)$ dla wszystkich $n \geqslant n_{0} \}$
Przykład:
$\sqrt n = \Omega (lg n)$ , gdzie $c=1, n_{0}=16$

Notacja $\Theta$ (tight bounds)

$\Theta (g(n))= \{ f(n):$ istnieją dodatnie stałe $c_{1}, c_{2}, n_{0}$ takie, że $0 \leqslant c_{1} g(n) \leqslant f(n) \leqslant c_{2} g(n)$ dla wszystkich $n \geqslant n_{0} \}$
Lub inaczej:
$\Theta (g(n))= O(g(n)) \cap \Omega (g(n))$
Przykład:
$5n^{2} -3n= \Theta (n^{2})$

Notacja o (małe O)

Notacje O i $\Omega$ są jak $\leqslant$ i $\geqslant$ .
Notacje o i $\omega$ sa jak $<$ i $>$ .

$o(g(n))= \{ f(n):$ dla każdej dodatniej stałej $c>0$ istnieje stała $n_{0}>0$ taka, że $0 \leqslant f(n) < cg(n)$ dla wszystkich $n \geqslant n_{0} \}$
Przykład:
$2n^{2} = o(n^{3})$ i $(n_{0}= {2 \over c})$

Notacja $\omega$

(patrz: Notacja o)
$\omega (g(n))= \{ f(n):$ dla każdej dodatniej stałej $c>0$ istnieje stała $n_{0}>0$ taka, że $0 \leqslant cg(n) < f(n)$ dla wszystkich $n \geqslant n_{0} \}$
Pzykład:
$\sqrt n =\omega (lg n)$ , gdzie $(n_{0} = 1+1/c)$