1.pdf

(119 KB) Pobierz
5. Ocena złożoności algorytmów
Teoria złożoności obliczeniowej to dział teorii obliczeń. Głównym jej celem jest określanie
ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami
są takie wielkości jak czas lub pamięć . Za twórców tej teorii uważani są Juris Hartmanis i Richard
Stearns.
1. Złożoność algorytmów
Ilość zasobów potrzebnych dla działania algorytmu może być rozumiana jako jego
złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej lub
pamięciowej . Oczywiście w więkoszości wypadków ilość potrzebnych zasobów będzie się różnić
w zależności od instancji problemu.
Jako przykład może nam posłużyć problem rozkładu liczb na czynniki pierwsze.
Domyślamy się, że (niezależnie od algorytmu) im większa liczba, tym więcej zasobów będzie
potrzebnych do jej rozłożenia. Taką własność ma znakomita większość problemów obliczeniowych:
im większy rozmiar danych wejściowych tym więcej zasobów (czasu, procesorów, pamięci) jest
potrzebnych do jego rozwiązania. Złożoność algorytmu jest więc funkcją rozmiaru danych
wejściowych.
Kolejnym problemem jest fakt, iż złóżoność nie zależy tylko i wyłącznie od rozmiaru
danych, ale może się znacznie różnić dla instancji o identycznym rozmiarze. Dwa często spotykane
sposoby radzenia sobie z tym problemem to: branie pod uwagę przypadków najgorszych (złożoność
pesymistyczna i pewien sposób uśrednienia wszystkich możliwych przypadków (złożoność
oczekiwana).
787969080.003.png
Złożoność czasowa
Przyjętą miarą złożoności czasowej jest liczba operacji podstawowych w zależności od
rozmiaru wejścia. Pomiar rzeczywistego czasu zegarowego jest mało użyteczny ze względu na silną
zależność od implementacji algorytmu, użytego kompilatora, maszyny na której algorytm
wykonano, a także umiejętności programisty. Dlatego w charakterze czasu wykonania rozpatrujemy
zwykle liczbę operacji podstawowych (dominujących). Operacjami podstawowymi mogą być na
przykład: podstawienie, porównanie lub prosta operacja arytmetyczna.
Kolejny problem polega na tym, w jakim języku programowania formułować algorytmy
oraz co można założyć o maszynie, na której algorytm ten będzie wykonywany. Istniejące
komputery różnią się miedzy sobą istotnymi (z punktu widzenia konstruowania algorytmów)
parametrami, jak na przykład liczba i rozmiar rejestrów, udostępnianymi operacjami
matematycznymi a ponadto podlegają ciągłym ulepszeniom. Wobec tego algorytmy analizuje się
wykorzystując abstrakcyjne modele komputera. Do popularnych modeli należą maszyna
wskaźnikowa i maszyna RAM.
Złożoność pamięciowa
Podobnie jak złożoność czasowa jest miarą czasu działania algorytmu, tak złożoność
pamięciowa jest miarą ilości wykorzystanej pamięci. Jako tę ilość najczęściej przyjmuje się użytą
pamięć maszyny abstrakcyjnej (na przykład liczbę komórek pamięci maszyny RAM) w funkcji
rozmiaru wejścia. Możliwe jest również obliczanie rozmiaru potrzebnej pamięci fizycznej
wyrażonej w bitach lub bajtach.
Typy złożoności
Weźmy na przykład algorytm wyszukiwania elementu w tablicy (od lewej od prawej strony)
int szukaj(int tab[n], int x)
{
while ((pos < n) && (tab
[pos] != x))
pos++;
if (pos < n)
return pos;
else
return -1;
}
787969080.004.png
Nie jest łatwo odpowiedzieć na pytanie odnośnie złożoności tego algorytmu. Jak zapewne się
domyślasz, algorytm może znaleźć wyszukiwany element dopiero pod koniec tablicy. Może też
znaleźć na początku. Nie mogąc precyzyjnie określić typu złożoności takiego rozwiązania (chociaż
tu jest prosty i można go oszacować na prawach O-notacji), zdefiniujemy 3 pojęcia:
• Złożoność pesymistyczna - jest to najgorszy możliwy przypadek danych wejściowych, gdzie
algorytm wykonuje się najdłużej, posiada najwięcej operacji dominujących, zabiera najwięcej
pamięci, wykorzystuje najwięcej wątków i tym podobne.
• Złożoność optymistyczna - przypadek, gdzie dane są tak dobrane, że występuje najmniejsza
ilość operacji dominujących i podobnych.
• Złożoność średnia - wartość oczekiwana zasobów wykorzystywanych przez program w
zwykłym przypadku.
Różnie podchodzi się do kwestii złożoności. Część programistów uważa, że wartość
optymistyczna jest mało interesującą informacją, inni - że wartość średnia. Bez wątpienia wartość
pesymistyczna jest informacją bardzo ważną, ponieważ będziemy wiedzieli ile należy przeznaczyć
zasobów do wykonania danego zadania. Wartość średnia jest bardzo przydatna, bo możemy
szacunkowo podać komuś czas wykonywania programu i bardzo często ile te program będzie się
wykonywał. Jednak wartość średnią oblicza się stosunkowo trudno i potrzeba tutaj dużej wiedzy z
dziedziny rachunku prawdopodobieństwa i statystyki matematycznej.
2. Porównanie złożoności algorytmu - Notacja „duże O”
Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze
wzrostem jej argumentów. Stosuje się je, w celu opisu złożoności obliczeniowej, czyli zależności
ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu.
Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od
konkretnej postaci tych zmian.
Do opisu asymptotycznego tempa wzrostu stosuje się notację dużego O . Notacja dużego O została
zaproponowana po raz pierwszy w roku 1894 przez niemieckiego matematyka Paula Bachmanna.
W późniejszych latach spopularyzował ją w swoich pracach Edmund Landau, niemiecki
matematyk, stąd czasem nazywana jest notacją Landaua.
787969080.005.png
Notacja „duże O”
Mówimy, że f jest co najwyżej rzędu g, gdy istnieją takie stałe n o > 0 oraz c> 0, że
Rząd złożoności obliczeniowej
W zależności od asymptotycznego tempa wzrostu, funkcję dzieli się na rzędy złożoności
obliczeniowej. Najczęściej wyróżnia się:
• O(1)- złożoność „rzędu 1” (stała) - liczba operacji wykonywanych przez algorytm jest w
przybliżeniu niezależna od rozmiaru problemu.
• O(logn)- złożoność logarytmiczna - liczba operacji rośnie proporcjonalnie do logarytmu z
rozmiaru problemu.
• O(n)- złożoność „rzędu n” (liniowa) - liczba wykonywanych przez algorytm operacji jest w
przybliżeniu proporcjonalna do rozmiaru problemu.
• O(nlogn)- złożoność liniowo-logarytmiczna (lub quasi-liniowa) - liczba operacji jest
proporcjonalna do iloczynu rozmiaru problemu przez jego logarytm.
• O(n 2 )- złożoność kwadratowa- liczba operacji rośnie proporcjonalnie do kwadratu rozmiaru
problemu.
• O(n c )- złożoność wielomianowa.
• O(c n )- złożoność wykładnicza.
• O(n!)- złożoność „rzędu n-silnia” - liczba operacji wzrasta proporcjonalnie do silni rozmiaru
problemu.
P, NP, Co-NP
Klasa P to wszystkie problemy decyzyjne, które można rozwiązać deterministycznym algorytmem
o złożoności wielomianowej (polynomial time).
Klasa NP to wszystkie problemy decyzyjne, które rozwiązuje niedeterministyczny algorytm
wielomianowy (non-deterministic polynomial).
Niedeterministyczny algorytm to taki który zawiera instrukcję: choice. Działa ona w sposób
losowy, a mianowicie zwraca losowo 0 bądź 1. Tak więc można powiedzieć, że instrukcja choice
odgaduje rozwiązanie. Algorytm przerywa działanie jeżeli odgadnięte rozwiązanie będzie
prawidłowe i zwraca wartość succes.
787969080.006.png 787969080.001.png
Przykładem problemu klasy NP jest pytanie "czy dana liczba jest złożona".Algorytm
niedeterministyczny dla tego problemu odgaduje kolejne bity dzielnika danej liczby. Kolejnym
krokiem jest sprawdzenie czy otrzymany w sposób niedeterministyczny podzielnik faktycznie dzieli
daną liczbę.
Klasa Co-NP to wszystkie problemy, których rozwiązania negatywne razem z odpowiednim
certyfikatem można potwierdzić w czasie wielomianowym.
Jeśli problem X należy do NP to problem NIE-X należy do Co -NP . Tak więc przykładowym
problemem klasy Co-NP może być pytanie "czy liczba jest pierwsza". Rozwiązanie negatywne,
którego certyfikatem jest dzielnik może być łatwo sprawdzone.
Klasa P jest oczywiście podzbiorem zarówno dla NP jak i dla Co-NP . Pytanie czy istnieją
problemy klasy NP które nie są problemami klasy P pomimo dziesiątek lat prób rozwiązania
pozostaje do dziś bez odpowiedzi.
Są trzy możliwe rozwiązania:
• P = NP
• P ≠ NP
• Problem jest w przyjętej aksjomatyce nierozwiązywalny
Przy czym pierwsze z nich wydaje się być mało prawdopodobne.
Źródła:
787969080.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin