Ten artykuł należy dopracować:

patrz dyskusja.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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.

1. od danych wejściowych (ciąg posortowany jest łatwiejszy do posortowania),
2. 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.

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

Zasugerowano, aby zintegrować ten artykuł z artykułem asymptotyczne tempo wzrostu (dyskusja). Nie opisano powodu propozycji integracji.

 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 ${\displaystyle T(n)\to \infty .}$

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

Przykład:

${\displaystyle 2n^{2}=O(n^{3}),gdzie(c=1,n_{0}=2).}$

Zwróć uwagę, że ${\displaystyle 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ć ${\displaystyle 2n^{2}\in O(n^{3}),}$ więc, np. ${\displaystyle O(n^{2})}$ jest zbiorem funkcji i we wzorach traktuje się ten zbiór jako anonimową funkcję ${\displaystyle h(n)\in O(n^{2}.}$)

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

Przykład:

${\displaystyle {\sqrt {n}}=\Omega (lgn),}$ gdzie ${\displaystyle c=1,n_{0}=16.}$

${\displaystyle \Theta (g(n))=\{f(n){:}}$ istnieją dodatnie stałe ${\displaystyle c_{1},c_{2},n_{0}}$ takie, że ${\displaystyle 0\leqslant c_{1}g(n)\leqslant f(n)\leqslant c_{2}g(n)}$ dla wszystkich ${\displaystyle n\geqslant n_{0}\},}$

lub inaczej:

${\displaystyle \Theta (g(n))=O(g(n))\cap \Omega (g(n)).}$

Przykład:

${\displaystyle 5n^{2}-3n=\Theta (n^{2}).}$

Notacje O i ${\displaystyle \Omega }$ są jak ${\displaystyle \leqslant }$ i ${\displaystyle \geqslant .}$

Notacje o i ${\displaystyle \omega }$ sa jak ${\displaystyle <}$ i ${\displaystyle >.}$

${\displaystyle o(g(n))=\{f(n){:}}$ dla każdej dodatniej stałej ${\displaystyle c>0}$ istnieje stała ${\displaystyle n_{0}>0}$ taka, że ${\displaystyle 0\leqslant f(n)<cg(n)}$ dla wszystkich ${\displaystyle n\geqslant n_{0}\}.}$

Przykład:

${\displaystyle 2n^{2}=o(n^{3})\quad {}}$ i ${\displaystyle {}\quad n_{0}={\frac {2}{c}}}$

(patrz: Notacja o)

${\displaystyle \omega (g(n))=\{f(n){:}}$ dla każdej dodatniej stałej ${\displaystyle c>0}$ istnieje stała ${\displaystyle n_{0}>0}$ taka, że ${\displaystyle 0\leqslant cg(n)<f(n)}$ dla wszystkich ${\displaystyle n\geqslant n_{0}\}.}$

Przykład:

${\displaystyle {\sqrt {n}}=\omega (lgn),}$ gdzie ${\displaystyle (n_{0}=1+1/c).}$

• teoria obliczeń
• złożoność obliczeniowa