Badanie złożoności algorytmów cz II 3

Praktyczne znaczenie złożoności obliczeniowej:

Różnica między złożonością O (N²) a O (W * log W) może oznaczać różnicę między miliardami a tylko setkami tysięcy operacji. Są problemy o prostych algorytmach, ale o ogromnej złożoności np. tzw. łamigłówka wieża Hanoi — przekładanie krążków z jednego kołka na drugi przy pomocy trzeciego. Da się dla tego zadania napisać bardzo prosty algorytm rekurencyjny fna ćwiczeniach¹), ale jego złożoność wynosi O (2^N), gdzie Njest liczbą krążków. Zatem dla przełożenia 64 krążków wykonując algorytm z szybkością miliona ruchów / sek. potrzeba 0.5 min lat. Tybetańczykom w legendzie miało to zająć czas do końca świata, ponieważ przenosząc 6 krążków/ min, musieliby pracować przez 5 bilonów lal t.j. dłużej niż według wszelkiej nasze wiedzy, będzie istniał Układ Słoneczny.

fylożnaby sądzić, że taka złożoność wynika z wielu czynności koniecznych do uzyskania rozyyiązania.

Sąjednak problemy, których wynik nie da się sprov-/adzić do rozstrzygnięcia tak — nie, a mających ogromną złożoność. Taki jest problem puzzli — układanki złożonej z N kwadratowych elementów, z których można ułożyć kwadrat o rozmiarach M x M (oczywiście N = M²). Okazuje się, że liczba możliwych ułożeń wynosi NI, gdybyśmy je chcieli sprawdzić wszystkie (np. żeby sprawdzić czy nie składają się na jakiś nieznany, ukryty rysunek).

Na przykład dla układanki 5x5 komputer sprawdzający milion ułożeń / sek. potrzebowałby na sprawdzenie wszystkich możliwości około 400 mld lat. czyli więcej niż wiek naszego Wszechświata oceniany na 15 mld lat od "Wielkiego Wybuchu".

Nie należy tego problemu mylić z zagadnieniem ułożenia puzzli mającego na celu odtworzenie jakiegoś znanego wzorcowego rysunku. Tu złożoność jest znacznie mniejsza. Bowiem na każdy kroku układanki możemy znaleźć brakujący element przeglądając wszystkie pozostałe nie ułożone elementy zamiast wszystkich możliwych kombinacji ułożenia. Z tego wynikałaby złożoność rzędu O (N²), zatem wiele, wiele razy mniejsza niż O (N!)

Funkcja N! jest bardzo szybko rosnącą z N. Szybciej rośnie tylko Nⁿ, wolniej od niej rosną K^N i N^K dla dowolnego skończonego k. Np. N! jest większa od N¹⁰⁰⁰ już dla N > 1165.

Niestety bardzo istotny problem złożoności obliczeniowej procesów decyzyjnych jest problemem typu N!

Generalnie w ocenach złożoności obliczeniowej stosuje się jej podział na złożoność wielomianowa i ponadwielomianowa. Problem o złożoności wielomianowej nazywamy łatwo rozwiązywalnymi. Te drugie trudno rozwiązywalnymi.

Problem złożoności pamięciowej (dygresja, ale nie zupełna)

Uzyskanie górnych i dolnych ograniczeń dla pamięciowych wymagań problemów algorytmicznych jest przedmiotem poważnych badań.

"Zasada nieokreśloności" dla czasu i pamięci:

Interesujące sątutaj nie tyle oddzielne ograniczenia dla czasu i pamięci, ale także łączne na iloczyn pamięci i czasu, gdzie za oszczędność czasu płacimy pamięcią i na odwrót. Usiłuje sie obecnie udowodnić, że te tzw. "kompromis czas — pamięć" istnieje . Zwykle prowadzi to do udowodnienia, że pamięć S i czas wykonania T dla pewnego algorytmu spełniają pewna relacje z danymi wejściowymi o długości N. np. załóżmy, że łącznie ograniczenie dolne i górne dla złożoności czasowo — pamięciowej (problem zamknięty) wynosi:

S² * T = O (N³ * (log N)²)

tzn., że jeśli zgodzimy się zużyć O (N³) czasu, to możemy zadanie rozwiązać zużywając O (log N) pamięci. Jeśli jednak chcemy ograniczyć czas wykonania do nie więcej niż O (N²), to będziemy potrzebować co najmniej

0(V/V- iog.\^r)

pamięci:

jeś/i toi

N³ *(log N)²

*/V*(logA0²

jeśli to I

s-

S*