Analiza algorytmów - Google

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

[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 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 sie 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 istanieje stała n0 > 0 taka, że 0 \leq f(n) < cg(n) dla wszystkich n \geq n_{0} \}
Przyklad:
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ż:


Unikalny cmentarz ugrofiński
Archeolodzy odkryli w okolicach miasta Suzdal w Rosji unikalne miejsce pochówku członków plemienia Ugrofinów, pochodzące z początków I tysiąclecia n.e. - donosi serwis internetowy icRussia.
Soczewki kontaktowe z elektronikÄ…
Opracowano prototyp nowoczesnych soczewek kontaktowych, w których wnętrzu zatopiony jest układ elektroniczny oraz diody LED. Jest to przysłowiowy "kamień milowy" dla dziedziny nauki, która zajmuje się miniaturyzacją układów scalonych, donosi "LaserFocusWorld".
Groźny detoks
Pewna Brytyjka doznała uszkodzeń mózgu po poddaniu się tzw. diecie "detoks", która wymagała picia dużych ilości płynów.
Pod lodami Arktyki 90 mld baryłek ropy
90 mld baryłek ropy i ilość gazu równa całym znanym jego zasobom w Rosji - na tyle oceniają amerykańscy eksperci rządowi zasoby Arktyki. Ich szacunki opisał w czwartek "Financial Times".
Twoje piersi tego nie lubiÄ…!
Kobiety, które noszą źle dobrane biustonosze, niszczą sobie piersi - alarmują naukowcy.
Linki: Strona g³ówna