Z Wikipedii

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: patrz dyskusja. 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ść.

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.

Spis treści 1 Od Czego zależy czas wykonywania 2 Rodzaje analizy 3 NOTACJA ASYMPTOTYCZNA 3.1 Notacja O (górna granica) 3.2 Notacja Ω (ograniczenie dolne) 3.3 Notacja Θ (tight bounds) 3.4 Notacja o (małe O) 3.5 Notacja ω 4 Zobacz też:

[edytuj] Od Czego zależy czas wykonywania

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);
3. zwykle szukamy górnych granic czasu działania, żeby mieć gwarancję.

[edytuj] Rodzaje analizy

1. Najgorszy przypadek (zwykle): T(n) = maksymalny czas działana 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 rozlożenia danych);
3. Najlepszy przypadek (oszukaństwo): Pokazuje, że nawet wolny algorytm pracuje szybko dla pewnych danych.

[edytuj] NOTACJA ASYMPTOTYCZNA

• ignoruj stale zależne od komputera (dzięki temu analiza jest uniwersalna, uzyskujemy te same wyniki niezależnie od maszyny);
• zwracaj uwagę na wzrost funkcji

[edytuj] Notacja O (górna granica)

O(g(n)) = {f(n): istnieją stałe c > 0,n₀ > 0 takie, że dla wszystkich

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

[edytuj] Notacja Ω (ograniczenie dolne)

Ω(g(n)) = {f(n): istnieją stałe c > 0,n₀ > 0 takie, że dla wszystkich
Przykład:
, gdzie c = 1,n₀ = 16

[edytuj] Notacja Θ (tight bounds)

Θ(g(n)) = {f(n): istnieją dodatnie stałe c₁,c₂,n₀ takie, że dla wszystkich
Lub inaczej:

Przykład:
5n² − 3n = Θ(n²

[edytuj] Notacja o (małe O)

Notacje O i Ω są jak i .
Notacje o i ω sa jak < i > .

o(g(n)) = {f(n): dla każdej dodatniej stałej c > 0 istanieje stała n₀ > 0 taka, że dla wszystkich
Przyklad:
2n² = o(n³) i

[edytuj] Notacja ω

(patrz: Notacja o)
ω(g(n)) = {f(n): dla każdej dodatniej stałej c > 0 istanieje stała n₀ > 0 taka, że dla wszystkich
Pzykład:
, gdzie (n₀ = 1 + 1 / c)

[edytuj] Zobacz też:

• Teoria obliczeń
• Złożoność obliczeniowa