Przykłady funkcji złożoności czasowej ZAOŻONOŚĆ ALGORYTMÓW 1. Algorytm sortowania bąbelkowego: Złożoność pamięciowa algorytmu dla listy o długości N jego złożoność może wyrazić funkcja wynika z liczby i rozmiaru struktur danych wykorzystywanych F(N) = liczbie porównań par sąsiednich elementów (?) w algorytmie; 2. Algorytm rozwiązywania problemu wież Hanoi: Złożoność czasowa algorytmu dla N krążków jego złożoność może wyrazić funkcja F(N) = liczba przeniesień pojedynczego krążka z kołka na kołek (?) wynika z liczby operacji elementarnych wykonywanych w trakcie przebiegu algorytmu. 3. Algorytm wyznaczania najdłuższej przekątnej wielokąta wypukłego: dla wielokąta o N wierzchołkach jego złożoność może ZAOŻONOŚĆ CZASOWA ALGORYTMU wyrazić funkcja zależność pomiędzy rozmiarem danych wejściowych a liczbą F(N) = liczba porównań długości dwóch przekątnych (?) wybranych operacji elementarnych wykonywanych w trakcie 4. Algorytm zachłanny wyznaczania najkrótszej sieci kolejowej : przebiegu algorytmu dla N miast i M możliwych do zbudowania odcinków jego (zależność podawana jako funkcja, której argumentem jest złożoność może wyrazić funkcja rozmiar danych, a wartością liczba operacji). F(N, M) = liczba porównań długości dwóch odcinków (?) Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 1 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 2 1. Przykład zmniejszenia liczby operacji w algorytmie W praktyce złożoność czasowa algorytmu Algorytm normalizacji wartości przechowywanych w tablicy decyduje często o jego przydatności jednowymiarowej względem wartości maksymalnej Dzieje się tak ponieważ: Dane wejściowe zapisane w tablicy T(K) dla K = 1, 2, ..., N trzeba rozwiązywać algorytmicznie coraz większe zadania: Alg. 1 1. wyznacz w zmiennej MAX największą z wartości; - w komputerowych systemach wspomagania decyzji, 2. dla K od 1 do N wykonuj co następuje: - przy komputerowych symulacjach i prognozach złożonych F1(N) = 2 " N " " " zjawisk. 2.1. T(K) ! T(K) " 100 / MAX rozwijane są komputerowe systemy czasu rzeczywistego: Alg. 2 1. wyznacz w zmiennej MAX największą z wartości - sterujące automatycznie złożonymi układami (transport, 2. ILORAZ ! 100 / MAX ; produkcja), 3. dla K od 1 do N wykonuj co następuje: - wyszukujące i przetwarzające duże ilości informacji. 3.1. T(K) ! T(K) " ILORAZ F2(N) = N +1 Chcemy zmniejszyć czas wykonania algorytmu poprzez Wybieramy operację elementarną, którą jest wyznaczenie zmniejszenie liczby wykonanych operacji elementarnych wartości iloczynu lub ilorazu dwóch zmiennych Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 3 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 4 2. Przykład zmniejszenia liczby operacji w algorytmie G S P T ? Algorytm (liniowego) wyszukiwania elementu z podanej listy ... Dane wejściowe to N elementów zapisanych w polach kluczowych 1. 2. N A.[P] N.[P] A.[T] = S listy wskaznikowej (pola rekordu: A kluczowe, N wskaznikowe; G wskaznik pierwszego rekordu) i szukany element podany w S. Alg. 2 1. wstaw rekord na koniec listy; A.[T] ! S ; G S P 2. P ! G ; F ! NIL ; ? 3. dopóki F = NIL wykonuj co następuje: ... 3.1. jeżeli S = A.[P] , to F ! P ; 1. 2. N A.[P] N.[P] F2(N) = N + 2 3.2. P ! N.[P] Alg. 1 1. P ! G ; F ! NIL ; 4. jeżeli F `" T, to odczytaj wartość wskaznika F. 2. dopóki P `" NIL i F = NIL wykonuj co następuje: Wybieramy operację elementarną, którą jest porównanie zawartości 2.1. jeżeli S = A.[P] , to F ! P ; wskazników P lub F z innym wskaznikiem lub adresem NIL 2.2. P ! N.[P] Badamy najgorszy przypadek Alg. 1 F1(N) = 2 " N + 1 " " " 3. jeżeli F `" NIL, to odczytaj wartość wskaznika F. Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 5 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 6 1 Poprawianie czasowej złożoności algorytmu jest czymś więcej, Jeżeli porównujemy dwa algorytmy wykonujące to samo niż tylko zmniejszaniem liczby operacji wykonywanych zadanie za pomocą jednej pętli ograniczonej, w której liczba w trakcie jego działania! powtórzeń (iteracji) jest wprost proporcjonalna do rozmiaru danych wejściowych N, to liczby operacji elementarnych Jak możemy stwierdzić, że złożoność została zmniejszona? (czasy wykonania) tych algorytmów w funkcji rozmiaru danych opisane są odpowiednio przez: Wykonując asymptotyczną analizę złożoności stwierdzamy jak szybko w miarę wzrostu rozmiaru danych wejściowych rośnie F1(N) = K1 + L1 " N funkcja złożoności podająca liczbę operacji wykonywanych w algorytmie (badamy tzw. rząd złożoności algorytmu). F2(N) = K2 + L2 " N Do porównania złożoności tych algorytmów możemy Jeżeli chcemy stwierdzić, który z dwóch algorytmów będących wykorzystać iloraz: rozwiązaniami tego samego problemu algorytmicznego ma F1 N ( ) istotnie niższą złożoność, to musimy porównać ich funkcje s N = ( ) F2 N ( ) złożoności i określić czy różnią się ich rzędy złożoności. Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 7 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 8 F1 N ( ) s N = W asymptotycznej analizie złożoności przyjęto, że porównując ( ) F2 N Wtedy spełnienie warunków: ( ) algorytmy badamy wartość ilorazu s(N) dla bardzo dużych wartości N, czyli formalnie jego granicę dla N ". s(N) = 1 oznaczałoby jednakową złożoność algorytmów, Zatem o wyniku porównania złożoności dwóch algorytmów s(N) < 1 oznaczałoby, że 1. algorytm ma niższą (lepszą) złożoność. decyduje wartość: Ale zauważmy, że s(N) = 1 zachodzi tylko wtedy, F1(N) lim s(N)= lim kiedy K1 = K2 i L1 = L2 , N " N " F2(N) co oznacza, że oba algorytmy są praktycznie identyczne. W przypadku porównywania dwóch funkcji liniowych będzie to A co mamy powiedzieć, wartość: kiedy s(N) e" 1 dla N d" N0, ale s(N) < 1 dla N > N0 . L1 lim s(N)= Który algorytm jest lepszy? N " L2 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 9 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 10 F czas wykonania 2 Przykład asymptotycznego Asymptotyczna analiza złożoności algorytmów porównania dwóch F 1 Dwa algorytmy opisane funkcjami F1(N) i F2(N) mają liniowych funkcji złożoności złożoność tego samego rzędu, jeśli L K 1 1 F1(N ) L 2 K F lim = C i zachodzi 0 < C < " " " " 1 1 K 2 iloraz K F N " F2(N ) 2 2 rozmiar danych N N 0 Sytuację, w której dwie funkcje złożoności są tego samego rzędu zapisujemy 1 Algorytm o funkcji F1(N) = Ś(F2(N)) (notacja theta) L złożoności F1 ma niższą 1 L 2 złożoność. rozmiar danych N N 0 Ale czy jest to złożoność Jeśli zachodzi F1(N) = Ś(F2(N)), to także F2(N) = Ś(F1(N)) niższa o rząd? Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 11 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 12 2 Algorytm opisany funkcją F1(N) ma złożoność nie wyższego Algorytm opisany funkcją F1(N) ma złożoność niższego rzędu niż algorytm opisany funkcją F2(N), jeśli rzędu niż algorytm opisany funkcją F2(N), jeśli F1(N ) F1(N ) lim = C i zachodzi C < " lim = 0 , czyli C = 0 " " " N " F2(N ) N " F2(N ) Sytuację, w której pierwsza funkcja złożoności jest nie Sytuację, w której pierwsza funkcja złożoności jest wyższego rzędu niż druga zapisujemy niższego rzędu niż druga zapisujemy F1(N) F2(N) p F1(N) = O(F2(N)) (notacja O duże) Badanie złożoności algorytmów w sposób asymptotyczny Jeśli zachodzi jednocześnie F1(N) = O(F2(N)) i F2(N) = O(F1(N)), prowadzi do wyróżnienia typowych rzędów złożoności: liniowa, to F1(N) = Ś(F2(N)). kwadratowa, Jeśli zachodzi F1(N) = Ś(F2(N)), to także F1(N) = O(F2(N)) . logarytmiczna, ... Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 13 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 14 Algorytm opisany funkcją F(N) ma złożoność liniową, jeśli Przypadek, w którym zachodzi warunek " N : 0 d" F(N) d" C < " oznaczamy F(N) = O(1) F(N ) " lim = C i zachodzi 0 < C < " " " N " N Dopiero obniżenie rzędu złożoności algorytmu jest istotnym Złożoność liniowa (rzędu N) oznaczana jest symbolem Ś(N) Ś Ś Ś ulepszeniem rozwiązania problemu algorytmicznego! Algorytm ma złożoność co najwyżej liniową, jeśli C < " ; oznaczenie O(N) Jeżeli algorytm może wykonywać różną liczbę operacji elementarnych dla danych wejściowych o tym samym rozmiarze, Algorytm opisany funkcją F(N) ma złożoność kwadratową, jeśli w zależności od konkretnego ich zestawu, to możemy badać jego F(N ) złożoność w najgorszym przypadku " lim = C i zachodzi 0 < C < " " " 2 (czyli skupiając się na takich przypadkach dopuszczalnych danych N " N wejściowych, dla których liczba operacji jest największa) Złożoność kwadratową (rzędu N2) oznaczana jest symbolem Ś(N2) Ś Ś Ś Algorytm ma złożoność co najwyżej kwadratową, jeśli C < " ; analiza złożoności najgorszego przypadku lub pesymistyczna oznaczenie O(N2) analiza złożoności średniego przypadku (trudniejsza) N N2 p Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 15 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 16 Porównanie złożoności przykładowych algorytmów Czy można zaproponować algorytm dla wyszukiwania normalizacji tablicy elementu z listy o pesymistycznej złożoności niższej niż liniowa? Złożoność czasowa algorytmu 1. wynosi F1(N) = 2 " N , czyli F1(N) = Ś(N) Szukamy zatem algorytmu, dla którego pesymistyczna Złożoność czasowa algorytmu 2. wynosi F2(N) = N + 1 , p funkcja złożoności spełniałaby warunek F(N) N. czyli F2(N) = Ś(N) F1(N) = Ś(F2(N)) Jeżeli założymy, że lista Y1, Y2, ..., YN jest uporządkowana, tzn. dla każdego i < j zachodzi Yi d" Yj , to takim algorytmem jest Porównanie złożoności przykładowych algorytmów wyszukiwanie binarne (przez połowienie) wyszukiwania elementu z listy (złożoność pesymistyczna) Jeśli dane wejściowe są zapisane w polach kluczowych Złożoność czasowa algorytmu 1. wynosi F1(N) = 2 " N + 1, rekordów z listy wskaznikowej o podanej w przykładzie czyli F1(N) = Ś(N) strukturze, to warunek uporządkowania ma postać: Złożoność czasowa algorytmu 2. wynosi F2(N) = N + 2 , dla każdego bieżącego wskaznika P zachodzi A.[P] d" A.[N.[P]] czyli F2(N) = Ś(N) F1(N) = Ś(F2(N)) Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 17 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 18 3 Algorytm wyszukiwania binarnego (z listy uporządkowanej) start Jeśli, jako zliczaną operację elementarną, wybierzemy porównanie elementu szukanego ze środkowym elementem Jako pierwszą listę bieżącą wez całą listę wejściową listy, to analiza złożoności będzie polegała po pierwsze na znalezieniu odpowiedzi na pytanie: ile razy w najgorszym przypadku jest powtarzana pętla w Czy środkowy NIE TAK element bieżącej algorytmie? listy jest tym szukanym? Wypisz znalazłem Czy szukany Czy szukany TAK NIE element jest mniejszy element jest mniejszy Najgorszy przypadek jest wtedy, kiedy na liście nie ma od elementu od elementu szukanego elementu; środkowego? środkowego? stop Po każdej iteracji długość bieżącej listy maleje o połowę i Jako listę bieżącą wez Jako listę bieżącą wez lewą połowę listy b. prawą połowę listy b. iteracje są przerywane, gdy jej długość osiągnie wartość 0. NIE TAK Wypisz Czy lista bieżąca nie ma jest pusta? Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 19 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 20 Zmiany w długości listy bieżącej: Skala poprawy złożoności (o rząd): start N N 1 + N po 1 iteracji N/2 łlg ł lgN N p 10 4 po 2 iteracji N/4 lg N 100 7 po 3 iteracji N/8 bo lim = 0 N " N 1 000 10 ... 10 000 14 K po K iteracji N 2 1 000 000 20 ... 1 000 000 000 30 M po przedostatniej iteracji Zatem M = log2N 1 = N 2 1 000 000 000 000 40 Pesymistyczna liczba iteracji F(N) = 1 + lgN = Ś(lgN) = O(lgN) 1 000 000 000 000 000 50 1 000 000 000 000 000 000 60 Algorytm wyszukiwania binarnego ma złożoność logarytmiczną Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 21 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 22 Przy asymptotycznej analizie złożoności o złożoności algorytmu decyduje, rosnąca w zależności od rozmiaru danych wejściowych, liczba wykonywanych iteracji (powtórzeń pętli) start Koszt K1 (1) Koszt K2 (2) Koszt K4 Całkowity koszt czasowy w najgorszym przypadku: F(N) = = K1+max(K3, K4)+K2"lgN stop (3) Koszt K3 = O(lgN) Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 23 4