Wprowadzenie do zlozonosci obliczeniowej
Short Description
Download Wprowadzenie do zlozonosci obliczeniowej...
Description
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Wprowadzenie do złożoności obliczeniowej mgr inż. Arkadiusz Chrobot Katedra Informatyki Politechniki Świętokrzyskiej
Kielce, 16 stycznia 2007
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Plan wykładu
1
Efektywność algorytmów
2
Złożoność obliczeniowa algorytmów
3
Notacje asymptotyczne
4
Przykłady
5
Uwagi na temat notacji asymptotycznych
6
Złożoność obliczeniowa problemów
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Plan wykładu
1
Efektywność algorytmów
2
Złożoność obliczeniowa algorytmów
3
Notacje asymptotyczne
4
Przykłady
5
Uwagi na temat notacji asymptotycznych
6
Złożoność obliczeniowa problemów
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Plan wykładu
1
Efektywność algorytmów
2
Złożoność obliczeniowa algorytmów
3
Notacje asymptotyczne
4
Przykłady
5
Uwagi na temat notacji asymptotycznych
6
Złożoność obliczeniowa problemów
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Plan wykładu
1
Efektywność algorytmów
2
Złożoność obliczeniowa algorytmów
3
Notacje asymptotyczne
4
Przykłady
5
Uwagi na temat notacji asymptotycznych
6
Złożoność obliczeniowa problemów
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Plan wykładu
1
Efektywność algorytmów
2
Złożoność obliczeniowa algorytmów
3
Notacje asymptotyczne
4
Przykłady
5
Uwagi na temat notacji asymptotycznych
6
Złożoność obliczeniowa problemów
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Plan wykładu
1
Efektywność algorytmów
2
Złożoność obliczeniowa algorytmów
3
Notacje asymptotyczne
4
Przykłady
5
Uwagi na temat notacji asymptotycznych
6
Złożoność obliczeniowa problemów
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Efektywność - dodatkowa własność algorytmów
D.E.Knuth „Sztuka programowania”: „Algorytm powinien być określony efektywnie w tym sensie, że jego operacje powinny być wystarczająco proste, by (przynajmniej teoretycznie) można było je dokładnie i w skończonym czasie wykonać za pomocą ołówka i kartki.”
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Efektywność - dodatkowa własność algorytmów
Definicja efektywności: Efektywnością algorytmu będziemy nazywać zapotrzebowanie jego implementacji (programu komputerowego) na zasoby (pamięć, czas procesora) zgromadzone w konkretnym systemie komputerowym.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Efektywność algorytmu zależy od:
architektury systemu komputerowego,
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Efektywność algorytmu zależy od:
architektury systemu komputerowego, konfiguracji sprzętowej systemu komputerowego
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Efektywność algorytmu zależy od:
architektury systemu komputerowego, konfiguracji sprzętowej systemu komputerowego rozmiaru danych wejściowych,
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Efektywność algorytmu zależy od:
architektury systemu komputerowego, konfiguracji sprzętowej systemu komputerowego rozmiaru danych wejściowych, porządku danych wejściowych.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Problemy
1
Jakiej miary użyć do wyrażenia efektywności (sekundy,cykle,bajty)?
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Problemy
1
Jakiej miary użyć do wyrażenia efektywności (sekundy,cykle,bajty)?
2
Jak porównywać poszczególne platformy systemowe?
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Maszyna wzorcowa Maszyna o dostępie swobodnym do pamięci Chcąc wyznaczyć efektywność działania algorytmu niezależnie od języka programowania, ani sprzętu na którym zostanie on zrealizowany, należy przyjąć jakąś maszynę wzorcową, która będzie wykonywała ten algorytm. Taką maszyną może być maszyna Turinga lub maszyna RAM. Ta ostatnia jest abstrakcyjnym, jednoprocesorowym komputerem, który dysponuje nieograniczoną pamięcią o dostępie swobodnym. Dostęp swobodny oznacza, że odwołanie do dowolnej lokacji tej pamięci (komórki) jest realizowane w takim samym czasie, niezależnie od jej położenia. Procesor tej maszyny ma krótką listę rozkazów, z których każdy jest zawsze wykonywany w takim samym czasie jak pozostałe. mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Złożoność obliczeniowa
Definicja Złożoność obliczeniowa wyznacza wielkość zasobów jakie potrzebne są do wykonania algorytmu w dowolnym systemie komputerowym.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Rodzaje złożoności obliczeniowej Złożoność czasowa Złożoność czasowa jest to zależność między rozmiarem i porządkiem danych wejściowych algorytmu, a czasem wykonania algorytmu. Rozmiar danych najczęściej jest wyrażany w liczbie elementów stanowiących dane wejściowe, natomiast czas jest wyrażany w przybliżonej liczbie kroków, jakie musi wykonać maszyna z pamięcią o dostępie swobodnym, by zakończyć wykonanie algorytmu.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Rodzaje złożoności obliczeniowej Złożoność czasowa Złożoność czasowa jest to zależność między rozmiarem i porządkiem danych wejściowych algorytmu, a czasem wykonania algorytmu. Rozmiar danych najczęściej jest wyrażany w liczbie elementów stanowiących dane wejściowe, natomiast czas jest wyrażany w przybliżonej liczbie kroków, jakie musi wykonać maszyna z pamięcią o dostępie swobodnym, by zakończyć wykonanie algorytmu.
Złożoność pamięciowa Złożoność pamięciowa jest to zależność pomiędzy rozmiarem i porządkiem danych wejściowych algorytmu, a jego zapotrzebowaniem na pamięć niezbędną do jego realizacji. Wielkość tej pamięci wyrażana jest w liczbie elementów, które należy przechować.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Analiza złożoności algorytmów
Złożoność obliczeniowa nie zależy od architektury i konfiguracji sprzętowej komputerów (wyznaczamy ją dla maszyny z pamięcią o dostępie swobodnym), ale zależy od rozmiaru i uporządkowania danych wejściowych. Wyznaczając złożoność obliczeniową algorytmu badamy trzy przypadki.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Analizowane przypadki wykonania algorytmów
Przypadek optymistyczny Zakładamy takie wstępne uporządkowanie danych wejściowych, że algorytm jest wykonywany najszybciej i wymaga najmniej pamięci do swojego działania.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Analizowane przypadki wykonania algorytmów
Przypadek pesymistyczny Zakładamy takie wstępne uporządkowanie danych wejściowych, że algorytm jest wykonywany najwolniej i wymaga najwięcej pamięci do swojego działania.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Czynniki wpływające na efektywność algorytmów Maszyna wzorcowa Złożoność obliczeniowa Analiza algorytmów
Analizowane przypadki wykonania algorytmów
Przypadek średni Badamy zapotrzebowanie algorytmu na pamięć i czas procesora dla najczęściej spotykanych uporządkowań danych wejściowych. Im ta złożoność jest bliższa złożoności przypadku optymistycznego, tym lepiej.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacje asymptotyczne
Najczęściej nie interesuje nas dokładne wyznaczenie złożoność obliczeniowej, wystarcza nam jej oszacowanie. Wynik takiego oszacowania najlepiej przedstawić za pomocą jednej z notacji asymptotycznych.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Θ
Θ(g (n)) = {f (n) : istnieją dodatnie stałe c1 , c2 , n0 takie, że 0 ¬ c1 · g (n) ¬ f (n) ¬ c2 · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Θ Θ(g (n)) = {f (n) : istnieją dodatnie stałe c1 , c2 , n0 takie, że 0 ¬ c1 · g (n) ¬ f (n) ¬ c2 · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Θ Θ(g (n)) = {f (n) : istnieją dodatnie stałe c1 , c2 , n0 takie, że 0 ¬ c1 · g (n) ¬ f (n) ¬ c2 · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Θ Θ(g (n)) = {f (n) : istnieją dodatnie stałe c1 , c2 , n0 takie, że 0 ¬ c1 · g (n) ¬ f (n) ¬ c2 · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Θ Θ(g (n)) = {f (n) : istnieją dodatnie stałe c1 , c2 , n0 takie, że 0 ¬ c1 · g (n) ¬ f (n) ¬ c2 · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja O
O(g (n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ¬ f (n) ¬ c · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja O O(g (n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ¬ f (n) ¬ c · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja O O(g (n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ¬ f (n) ¬ c · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja O O(g (n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ¬ f (n) ¬ c · g (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Ω
Ω(g (n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ¬ c · g (n) ¬ f (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Ω Ω(g (n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ¬ c · g (n) ¬ f (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Ω Ω(g (n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ¬ c · g (n) ¬ f (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacja Ω Ω(g (n)) = {f (n) : istnieją dodatnie stałe c, n0 takie, że 0 ¬ c · g (n) ¬ f (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Notacja Notacja Notacja Notacje
wielkie wielkie wielkie małe o
theta o omega i małe omega
Notacje o i ω
Notacja o o(g (n)) = {f (n) : dla każdej dodatniej stałej c > 0, istnieje stała n0 > 0 taka, że 0 ¬ f (n) < c · g (n) dla wszystkich n n0 } Notacja ω ω(g (n)) = {f (n) : dla każdej dodatniej stałej c > 0, istnieje stała n0 > 0 takie, że 0 ¬ c · g (n) < f (n) dla wszystkich n n0 }
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Przykład pierwszy Przykład drugi
Złożoność czasowa algorytmu insertionsort
for j:=low(t)+1 to high(t) do begin key:=t[j]; i:=j-1; while (i>0) and (t[i]>key) do begin t[i+1]:=t[i]; i:=i-1; end; t[i+1]:=key; end;
koszt c1
mgr inż. Arkadiusz Chrobot
liczba wykonań n
c2 c3 c4
n-1 n-1 Pn
c5 c6
Pn (t − 1) Pnj=2 j (t j=2 j − 1)
c7
n-1
j=2 tj
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Przykład pierwszy Przykład drugi
Ogólne równanie na czas działania algorytmu insertionsort
T (n) = c1 · n + c2 · (n − 1) + c3 · (n − 1) + c4 · Pn Pn j=2 (tj − 1) + c6 · j=2 (tj − 1) + c7 · (n − 1)
mgr inż. Arkadiusz Chrobot
Pn
j=2 tj
+ c5 ·
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Przykład pierwszy Przykład drugi
Przypadek optymistyczny dla insertionsort
Algorytm sortowania przez wstawianie najszybciej jest wykonywany, kiedy musi posortować tablicę już posortowaną (tj = 1): T (n) = c1 · n + c2 · (n − 1) + c3 · (n − 1) + c4 · (n − 1) + c7 · (n − 1) = (c1 + c2 + c3 + c4 + c7 ) · n − (c2 + c3 + c4 + c7 ) Jeśli teraz przyjmiemy, że a = c1 + c2 + c3 + c4 + c7 , a b = c2 + c3 + c4 + c7 to możemy powyższe równanie zapisać jako T (n) = a · n − b
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Przykład pierwszy Przykład drugi
Przypadek pesymistyczny
Algorytm sortowania przez wstawianie wykonywany jest najwolniej, kiedy musi posortować tablicę posortowaną odwrotnie (tj = j). W takim przypadku Pn Pn n·(n+1) −1 j=2 j = j=2 tj = 2 i
Pn
j=2 (tj
− 1) =
Pn
j=2 (j
− 1) =
mgr inż. Arkadiusz Chrobot
n·(n−1) 2
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Przykład pierwszy Przykład drugi
Przypadek pesymistyczny Zatem: T (n) = c1 · n + c2 · (n − 1) + c3 · (n − 1) + c4 n·(n+1) − 1 + c5 · 2 n·(n−1) + c6 · n·(n−1) + c7 · (n − 1) = 2 2 c4 c5 c6 2 + c +c +c + c4 − c5 − c6 +c ·n−(c +c +c +c ) + + ·n 1 2 3 2 3 4 7 7 2 2 2 2 2 2 Jeżeli przyjmiemy, że a = c24 + c25 + c26 , b = c1 + c2 + c3 + c24 − c25 − c26 + c7 i c = c2 + c3 + c4 + c7 To możemy zapisać powyższe równianie jako: T (n) = a · n2 + b · n − c
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Przykład pierwszy Przykład drugi
Użycie notacji asymptotycznych
Używając notacji asymptotycznych zwracamy uwagę na ten człon równania opisującego czas, który ma największe znaczenie i pomijamy wszelkie stałe. W przypadku optymistycznego przypadku czas działania algorytmu insertionsort możemy wyrazić jako To (n) = Θ(n), w przypadku pesymistycznym jako Tp (n) = Θ(n2 ). Ogólnie możemy napisać, że czas działania algorytmu insertionsort wynosi T (n) = O(n2 ) (jest to asymptotyczna granica górna czasu działania tego algorytmu wiemy, że gorzej być nie może).
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Przykład pierwszy Przykład drugi
Przypadek średni
Analiza przypadku średniego (lub oczekiwanego) może być złożona, ze względu na określenie „średnich” danych wejściowych. Dosyć często przyjmuje się (jeśli jest to uzasadnione), że przypadek średni jest równy przypadkowi pesymistycznemu.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Przykład pierwszy Przykład drugi
Oszacowanie rzeczywistego czasu wykonania
Załóżmy, że mamy algorytm sortowania, którego złożoność czasowa wynosi O(n2 ). Dla tablicy o stu elementach (n=100) wykonywał się on przez dwie sekundy. Ile będzie wykonywał się ten algorytm dla jeśli tablica będzie miała 106 elementów? Czas ten 106 2 obliczamy następująco: t = 2 · 102 = (2 · 104 )2 = 4 · 108 sekund.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Zależność między notacjami O, Θ i Ω
Jeśli asymptotyczna granica dolna (notacja O) i asymptotyczna granica dolna (notacja Ω) są sobie równe, to możemy podać asymptotycznie dokładne oszacowanie czasu działania algorytmu (notacja Θ).
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Pułapki stosowania notacji asymptotycznych
Stosując notacje asymptotyczne podajemy oszacowania czasu działania algorytmu lub jego wymagania co do pamięci, dla rozmiaru danych dążącego do nieskończoności, dlatego wolno nam zaniedbać stałe i niektóre mniej ważne człony w równaniach. Niestety te „nieistotne” stałe mogą mieć bardzo duży wpływ na np. czas działania algorytmu, jeśli jest on wykonywany dla danych o niewielkim rozmiarze. W ten sposób algorytm o złożoności czasowej O(n2 ) może okazać się wydajniejszy od O(n).
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Pułapki stosowania notacji asymptotycznych
Podając złożoność obliczeniową algorytmów z zastosowaniem notacji asymptotycznej podajemy jedynie rząd wielkości. Może się więc okazać, że dwa algorytmy należące do tej samej klasy złożoności nie zachowują się tak samo w codziennych zastosowaniach (np. bubblesort i selectionsort). W takich wypadkach konieczna jest dokładniejsza ocena ich złożoności (np. poprzez policzenie liczby porównań lub liczby wymian).
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Porównanie różnych klas złożoności algorytmów
O(1) - 1µs O(n) - 1s O(n2 ) - 11,6 dni O(n3 ) - 32000 lat O(2n ) - 10301006 · wiek wszechświata
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Złożoność obliczeniowa problemów Złożoność obliczeniowa jest nie tylko cechą algorytmów, ale również cechą problemów, które one rozwiązują.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Złożoność obliczeniowa problemów Problemy zaliczane do klasy P są rozwiązywane przez deterministyczne algorytmy działające w czasie wielomianowym. Problemy klasy NP są problemami rozwiązywanymi przez algorytmy niedeterministyczne działające w czasie wielomianowym. Podklasą tych problemów są problemy należące do klasy NP-zupełnych (ang. NP-complete). Zakłada się, że znalezienie algorytmu deterministycznego, który rozwiązywałby choć jeden z tych problemów w czasie wielomianowym, mogłoby doprowadzić do znalezienia algorytmów działających w tym czasie dla wszystkich pozostałych problemów należących do tej klasy.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
Plan Efektywność algorytmów Złożoność obliczeniowa Notacje asymptotyczne Przykłady Uwagi na temat notacji asymptotycznych Złożoność obliczeniowa problemów
Złożoność obliczeniowa problemów
Problemy należące do klasy PSPACE mają wielomianową złożoność pamięciową. Zakłada się, że są one trudniejsze od problemów należących do klasy NP. Klasa PSPACE-zupełne (PSPACE-complete) jest odpowiednikiem klasy NP-complete. Największą złożoność obliczeniową (wykładniczą) mają problemy należące do klasy EXPTIME.
mgr inż. Arkadiusz Chrobot
Wprowadzenie do złożoności obliczeniowej
View more...
Comments
