Analiza algorytmów - Nauka

Analiza algorytmów

Z Wikipedii

Skocz do: nawigacji, szukaj
 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 znajdują się na stronie dyskusji tego artykułu w sekcji Dopracować
Po wyeliminowaniu wskazanych powyżej niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu 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.

Spis treści

[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);

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

[edytuj] Rodzaje analizy

  1. Najgorszy przypadek (zwykle): 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.

[edytuj] Notacja asymptotyczna

Merge arrow
 Zasugerowano, aby ten artykuł (lub sekcję) zintegrować z artykułem asymptotyczne tempo wzrostu. (dyskusja)
Zobacz więcej w osobnym artykule: asymptotyczne tempo wzrostu.
  • ignoruj stałe zależne od komputera (dzięki temu analiza jest uniwersalna, uzyskujemy te same wyniki niezależnie od maszyny);
  • zwracaj uwagę na wzrost funkcji T(n) \to \infty

[edytuj] Notacja O (górna granica)

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

Przykład: 2n2 = O(n3),gdzie(c = 1,n0 = 2)
Zwróć uwagę, że n2,n3 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(n2) jest zbiorem funkcji i we wzorach traktuje się ten zbiór jako anonimową funkcję h(n) \in O(n^{2} ).

[edytuj] Notacja Ω (ograniczenie dolne)

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

[edytuj] Notacja Θ (tight bounds)

Θ(g(n)) = {f(n): istnieją dodatnie stałe c1,c2,n0 takie, że 0 \leq c_{1} g(n) \leq f(n) \leq c_{2} g(n) dla wszystkich n \geq n_{0} \}
Lub inaczej:
\Theta (g(n))= O(g(n)) \cap \Omega (g(n))
Przykład:
5n2 − 3n = Θ(n2)

[edytuj] Notacja o (małe O)

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

o(g(n)) = {f(n): dla każdej dodatniej stałej c > 0 istnieje stała n0 > 0 taka, że 0 \leq f(n) < cg(n) dla wszystkich n \geq n_{0} \}
Przykład:
2n2 = o(n3) i (n_{0}= {2 \over c})

[edytuj] Notacja ω

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

[edytuj] Zobacz też:






Palenie w pracy - już nie można ignorować tego problemu
Temat ogólnie pojętego palenia papierosów coraz bardziej dotyka pracodawców. Kiedy wreszcie uznano, że palenie tytoniu nie jest jedną z wielu niegroźnych używek, lecz prawdziwym uzależnieniem, które nie tylko degraduje organizm,...
Wolontariat pracowniczy. Dobrzy ludzie w mądrych firmach.
Dzięki wprowadzeniu programu wolontariatu pracowniczego firma ma możliwość sprawdzenia się w niesieniu pomocy potrzebującym. Pracownicy, stając się wolontariuszami, dzielą się swoim doświadczeniem zawodowym, wiedzą i umiejętnościami. Praca dla dobra innych...
Pracująca Mama
Kodeks pracy gwarantuje kobietom w ciąży i młodym mamom rozmaite prawa. Nie zawsze o nich wiemy, a w dodatku nie wszyscy pracodawcy chętnie o nich informują. Dlatego warto się z...
Ekspert odpowiada: Data wystawienia zwolnienia lekarskiego
PYTANIE: Zwolnienie zostało wystawione pracownikowi przez lekarza z datą 14 stycznia na okres od 11 do 24 stycznia. Na ile dni wstecz lekarz może wystawić zwolnienie lekarskie?
Ekspert odpowiada: Jak bezbłędnie wyliczyć trzynastkę?
PYTANIE: Jak bezbłędnie wyliczyć trzynastkę?

906 906 no host sprawdz strone wymiana linkow