TI/Algorytmy i struktury danych/Złożoność obliczeniowa i pamięciowa - Historia wersji

http://brain.fuw.edu.pl/edu/index.php?action=history&feed=atom&title=TI%2FAlgorytmy_i_struktury_danych%2FZ%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa_i_pami%C4%99ciowa TI/Algorytmy i struktury danych/Złożoność obliczeniowa i pamięciowa - Historia wersji 2026-05-03T16:24:27Z Historia wersji tej strony wiki MediaWiki 1.34.1 http://brain.fuw.edu.pl/edu/index.php?title=TI/Algorytmy_i_struktury_danych/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa_i_pami%C4%99ciowa&diff=1938&oldid=prev Jarekz: Utworzono nową stronę " <!--= szkic = * '''trochę o tym, jak taki program będzie się wykonywał w uproszczony sposób: zaujmuje jakieś miejsce w RAM oraz wykonuje różne instreukcje po ko..." 2015-05-23T13:51:28Z

<p>Utworzono nową stronę " <br /> <br /> = Złożoność obliczeniowa i pamięciowa = <br /> <br /> == Złożoność obliczeniowa -- założenia ==<br /> <br /> <br /> Jak wiadomo, czas wykonania programu może się różnić w zależności od tego na jak silnym komputerze zostanie on wykonany. Dlatego w dla potrzeb teoretycznego porównywania złożoności czasowej różnych algorytmów, nie mierzymy jej w sekundach, tylko abstrakcyjnych jednostkach -- ilości "operacji dominujących", czyli takich, które znacząco wpływają na czas wykonania programu.<br /> <br /> Wskaż operacje dominujące w poniższych programach:<br /> <source lang="python"><br /> def suma(a,b):<br /> wynik = a + b<br /> return wynik<br /> </source><br /> <br /> <source lang="python"><br /> def operacje(a,b):<br /> suma = a+b<br /> iloczyn = a*b<br /> iloraz = a/b<br /> roznica = a - b<br /> return suma, iloczyn, roznica, iloraz<br /> </source> <br /> <br /> <br /> <source lang="python"><br /> def wypisz(a,b):<br /> print operacje(a,b)<br /> </source><br /> (Wywołanie funkcji która ma 4 instrukcje, będzie trwać 4 instrukcje)<br /> <br /> <br /> Znajdowanie Maximum: Danych jest N różnych liczb, nazwanych A[1], ... , A[N]. Wskaż największą.<br /> <br /> m = A[1]<br /> imax = 1 <br /> for i = t to N do:<br /> if A[i] > m:<br /> m = A[i]<br /> imax = i<br /> <br /> <br /> Problem: Wskaż index wystapienia liczby 0 w danej tablicy. Wiadomo, że występuje dokładnie raz.<br /> <source lang="python"><br /> for i=1 1 to N do:<br /> if A[i] = 0:<br /> return i<br /> <br /> </source><br /> <br /> Jaki będzie koszt dla danych:<br /> A[1] = 1, A[2] = 0, A[3] = 1, A[1000] = 1<br /> <br /> A dla danych:<br /> A[1] = 1, ... , A[999] = 1, A[1000] = 0<br /> <br /> <br /> Sortowanie bąbelkowe:<br /> <br /> sort(T)<br /> for i=0 to n-2 do<br /> for j=n-1 downto i+1 do<br /> if (t[j-1]>t[j])<br /> zamień t[j] i t[j-1]<br /> <br /> * Która operacja jest tu operacją, którą bierzemy pod uwage przy szacowaniu kosztu?<br /> * Ile będzie trwało sortowanie dla tablicy:<br /> ** t[1] = 2, t[2] = 3, t[3] = 1, t[4] = 4, ..., t[100] = 100<br /> ** t[1] = 2, t[2] = 3, t[3] = 1, t[4] = 4, t[5] = 6, t[6] = 5, ..., t[100] = 100<br /> <br /> * A jakie są najgorsze możliwe dane? Ile wtedy będzie trwało wykonanie programu?<br /> <br /> Na tym właśnie polega szacowanie kosztu pesytmistycznego -- czas trwania programu dla najgorszych możliwych danych.<br /> <br /> == Koszt pesymistyczny i oczekiwany ==<br /> <br /> Dla zainteresowanych koszty różnych operacji w pythonie [http://wiki.python.org/moin/TimeComplexity tutaj]<br /> <br /> <br /> <br /> === Ćwiczenia ===<br /> <br /> * Jakie będą złożoności obliczeniowe następujących pętli:<br /> <source lang="python"><br /> for i in range(n)<br /> print i<br /> <br /> <br /> for j in range(n)<br /> for i in range(n)<br /> print i, j<br /> <br /> <br /> for j in range(n):<br /> for i in range(j):<br /> <br /> <br /> n=1<br /> while(n < =x):<br /> print n<br /> n=2*n<br /> <br /> <br /> h=n<br /> while(h > 0):<br /> for i in range(n):<br /> print i<br /> h=h/2<br /> <br /> </source><br /> <br /> === Notacja duże "O" i rzędy wielkości ===<br /> Notacja duże "O" (inaczej: notacja asymptotyczna, notacja Landaua) służy do opisywania asymptotycznego zachowania funkcji (czyli zachowania funkcji wraz ze wzrostem jej argumentów).<br /> <br /> Definicja:<br /> <br /> f(x) = O(g(x)) <=> istnieje c>0 i x_0 > 0 takie, że dla każdego x > x_0 zachodzi f(x) <= cg(x) <br /> <br /> Oznacza to, że f jest co najwyżej rzędu g.<br /> <br /> Porównywanie złożoności:<br /> <br /> 1 < lg(lg(n)) < lg(n) < sqrt(n) < n < nlg(n) < n^2 < n^3 < n^{lg(n)} < 2^n < n! < n^n <2^{2^n}<br /> <br /> ==== Ćwiczenie ====<br /> <br /> * Załóżmy, że algorytmy A i B rozwiązują ten sam problem. Niech program A ma koszt pesymistyczny 100*n*log2(n), a program B n^2.<br /> <br /> ** Czy zawsze bardziej się opłaca użyć algorytmy A?<br /> ** Co będzie dla danych, gdzie n >> 10000 ?<br /> ** Co będzie dla danych, gdzie n << 100 ?<br /> <br /> === Sortowanie przez wstawianie ===<br /> <br /> <br /> Elementy tablicy od 1 do i - 1 są posortowane, w kolejnym kroku należy w odpowiednie miejsce wstawić element a[i], w tym celu szukamy pierwszego elementu mniejszego od a[i] występującego przed nim i aktualny element wstawiamy bezpośrednio za nim (wymaga to przesunięcia wszystkich elementów za znalezionym o jedno miejsce w prawo)<br /> <br /> for i := 2 to n do<br /> begin<br /> x := a[i];<br /> j := i - 1;<br /> while (j > 0) and (a[j] > x) do<br /> begin<br /> a[j - 1] := a [j];<br /> j := j - 1;<br /> end;<br /> a[j] := x;<br /> end;<br /> <br /> Operacjami dominującymi są przypisania w liniach 3 i 7<br /> <br /> Gdy tablica a na początku jest już posortowana rosnąco to operacja dominująca wykona się dokładnie n - 1 = O(n) razy (nigdy nie będzie spełniony warunek a[j] > x), a w sytuacji gdy będzie ona posortowana malejąco to warunek ten będzie zawsze spełniony, zatem dla k-tego przebiegu for pętli pętla while wykona się k - 1 razy, zatem złożoność obliczeniowa to: 1 + 2 + 3 + ... + (n - 1) + n = n(n - 1) / 2 + n - 1 = O(n^2), widać, zatem, że złożoność może zależeć od danych wejściowych<br /> <br /> Na szczęście gorzej już się nie da - o drugim przypadku mówimy, że jest pesymistyczny, a jego złożoność nazywamy złożonością pesymistyczną.<br /> <br /> ==== Złożoność oczekiwana ====<br /> <br /> W codziennej praktyce spotykamy dość rzadko dane realizujące złożoność pesymistyczną, zatem nasuwa się pytanie jak szybko będzie działał nasz program zazwyczaj, czyli chcemy znać złożoność oczekiwaną bądź średnią.<br /> <br /> Zastanówmy się najpierw od czego zależy liczba przypisań w linii 7, jest ona związana z liczbą inwersji, czyli liczbą takich par (i,j), że j > i i a[j] < a[i], oznaczmy ją inv(a), wtedy liczba wykonań operacji dominującej to n - 1 + inv(a), zatem jeśli inv(a) = O(n) to złożoność całego algorytmu jest O(n), a gdy inv(a) = O(n^2) to taka jest również złożoność algorytmu.<br /> <br /> Postarajmy się teraz obliczyć średnią liczbę inwersji w losowej permutacji.<br /> <br /> Do obliczania złożoności oczekiwanej przydatna jest znajomość rachunku prawdopodobieństwa, n-elementowych permutacji mamy n!, załóżmy, że każda jest równie prawdopodobna<br /> <br /> Pozostaje teraz policzyć ile jest permutacji mających dokładnie k inwersji, pomocnym do tego będzie wprowadzenie pojęcia wektora inwersji permutacji, czyli ciąg w[i], gdzie w[i] to liczba elementów występujących na lewo od a[i] w ciągu a i większych od a[i], czytelnikowi pozostawiamy udowodnienie bijekcji między permutacją i odpowiadającym jej wektorem inwersji, oczywiste jest, że suma elementów wektora inwersji jest równa liczbie inwersji permutacji, na pozycji i w wektorze inwersji mogą się znaleźć (z równym prawdopodobieństwem wynoszącym 1/i) liczby od 0 (gdy a[i] jest większe od wszystkich poprzednich) do i - 1 (gdy a[i] jest mniejsze od wszystkich poprzednich), zatem wartość oczekiwana i-tego elementu to (0 + 1 + 2 + ... + (i - 1)) / i = (i - 1) / 2, a wartość oczekiwana sumy elementów wektora inwersji to 0 + 1 / 2 + 2 / 2 + ... + (n - 1) / 2 = n(n - 1) / 4<br /> <br /> Zatem dla losowej permutacji a mamy inv(a) = n(n - 1) / 4, zatem oczekiwana złożoność algorytmu sortowania przez wstawianie to: n(n - 1) / 4 + n - 1 = O(n^2)<br /> <br /> == Zadania ==<br /> <br /> * wymyśl program, którego złożoność będzie wynosiła:<br /> ** O(n^2) (np. psortowanie bąbelkowe, sortowanie przez wstawianie (insertion sort), sortowanie przez wybór (selection sort))<br /> ** O(n!) (dopasowywanie kwadracików z dzióbkami - układanka, problem skoczka)<br /> ** O(n) (szukanie lidera, szukanie najdłuższego niespójnego ciągu rosnącego)<br /> ** O(1) <br /> ** O(2^n) (obliczanie liczby Fibonacciego, wieże Hanoi)<br /> ** O(lg(n)) (wyszukiwanie binarne)<br /> ** O(nlg(n)) <br /> <br /> <br /> <br /> <br /> <br /> <br /> === Przykłady ===<br /> <br /> Problem sortowania: dana jest tablica należy ją posortować, czyli ustawić jej elementy w kolejności rosnącej (albo malejącej)<br /> <br /> ==== Sortowanie bąbelkowe ==== <br /> Badamy tablicę od początku jeśli znajdziemy takie i, że a[i + 1] < a[i] to zamieniamy elementy, po jednym przejściu tablicy na ostatnim miejscu otrzymujemy największy element tablicy, problem redukuje się zatem do tablicy krótszej o 1<br /> <br /> for i := 1 to n - 1 do<br /> begin<br /> for j := 1 to n - i + 1 do <br /> begin<br /> if a[j + 1] < a[j] then<br /> swap(a[j + 1], a[j]);<br /> end;<br /> end;<br /> <br /> ==== Sortowanie przez wstawianie ==== <br /> <br /> patrz opis złożoności pesymistycznej i oczekiwanej<br /> <br /> ==== Sortowanie przez wybór ====<br /> Przechodzimy tablicę szukając elementu największego zamieniamy go z ostatnim po czym problem redukuje się do sortowania tablicy krótszej o 1<br /> <br /> for i := 1 to n do<br /> begin<br /> max := a[i];<br /> maxIndex := i;<br /> for j := 1 to n - i + 1 do<br /> begin<br /> if a[j] > max then<br /> begin<br /> max := a[j];<br /> maxIndex := j;<br /> end;<br /> end;<br /> swap(a[maxIndex], a[n - i + 1]);<br /> end;<br /> <br /> ==== Dopasowanie kwadracików z dzióbkami :-)====<br /> M<br /> amy dane m = n^2 kwadracików przy każdym boku kwadratu wewnątrz niego znajduje się kolorowy trójkąt, należy sprawdzić czy istnieje takie ułożenie kwadratów w jeden duży o boku n, że wszystkie trójkąty pasują do siebie - najprostsze rozwiązanie to sprawdzenie wszystkich możliwości których jest m!<br /> <br /> ==== Szukanie lidera ==== <br /> <br /> dany jest ciąg a[1..n], problem polega na znalezieniu elementu występującego w nim więcej niż n/2 razy, rozwiązanie brutalne to sprawdzenie liczności występowania każdego z elementów - złożoność kwadratowa, można to jednak zrobić w czasie liniowym :-)<br /> <br /> wystapienia := 0;<br /> for i := 1 to n - 1 do<br /> begin<br /> if wystapienia = 0 then<br /> begin<br /> kandydat := i;<br /> wystapienia := 1;<br /> end;<br /> if a[i] = a[i + 1] then<br /> wystapienia := wystapienia + 1;<br /> else<br /> wystapienia := wystapienia - 1;<br /> end;<br /> <br /> w zaskakujący automagiczny sposób jeśli w tablicy występował lider to jest nim a[kandydat], sprawdzić czy jest on liderem możemy oczywiście w czasie liniowym<br /> <br /> ==== Szukanie najdłuższego niespójnego podciągu rosnącego (malejącego) ====<br /> <br /> Najbardziej brutalna metoda to wygenerowanie wszystkich 2^n podciągów i sprawdzanie po kolei, ale da się to zrobić w czasie O(nlogn).<br /> <br /> <br /> <br /> <br /> <source lang="python"><br /> odp = 1<br /> for i in range(n): <br /> x = a[i]<br /> a[i] = 0<br /> # poniezej szukamy minimalnego j, t. ze j<= i, oraz x >= a[j]<br /> <br /> while (j >= 0) and (x >= a[j]):<br /> j := j - 1<br /> a[j] = x<br /> odp = max(j, odp)<br /> </source><br /> <br /> Powyższy algorytm rozwiązuje problem wciąż w czasie O(n^2), ale można go łatwo sprowadzić do O(nlogn) dzięki temu, że początek tablicy, w którym wyszukujemy minimum, będzie zawsze posortowany i możemy zastosować przeszukiwanie binarne.<br /> <br /> ==== Obliczanie liczby Fibonacciego ====<br /> Liczbę Fibonacciego definiuje się rekurencyjnie: <math>F_0 = 0; F_1 = 1; F_{n} = F_{n - 1} + F_{n - 2}</math>, można ją liczyć z definicji daje to <math>2^n</math> dodawań, są do tego inne techniki można na przykład zaalokować dodatkową zmienną i trzymać w niej poprzedni wynik korzystając z niego i aktualizując go za każdym razem &mdash; daje to złożoność liniową, można robić to metodą mnożenia macierzy, co przy zastosowaniu metody mnożenia chłopków syberyjskich da złożoność logarytmiczną i w końcu dla większych <math>n</math> można skorzystać ze wzoru Bineta i dostać przybliżony wynik w czasie stałym.<br /> [[Tytuł linku]]<br /> <br /> ==== Wieże Hanoi ==== <br /> Wyobraźcie sobie trzy słupy na jeden z nich są nasunięte krążki o malejącym idąc w górę promieniu, zasady: możecie kłaść krążek tylko na krążek o większej średnicy albo wkładać na pusty słup, zadanie dla Was przełożyć n krążków ze słupa numer 1 na słup numer 2 korzystając ze słupa numer 3, czas start! jeśli przełożycie 64 takich krążków to zgodnie z wierzeniami tybetańskich mnichów nastąpi koniec świata (biorąc pod uwagę złożoność jest to możliwe), jak to zrobić? jednym ze sposobów jest podejście rekurencyjne, zadanie sprowadza się do:<br /> <br /> przełożyć n - 1 krążków ze słupa numer 1 na słup numer 3 korzystając ze słupa numer 2<br /> przełożyć krążek ze słupa numer 1 na słup numer 2<br /> przełożyć n - 1 krążków ze słupa numer 3 na słup numer 2 korzystając ze słupa numer 1<br /> <br /> daje to złożoność 2^n<br /> <br /> ==== Wyszukiwanie binarne ==== <br /> Legenda głosi, że był kiedyś teleturniej w którym występowały dwie drużyny, jedna wymyślała słowo, a druga miała za zadanie zadając określoną liczbę pytań odgadnąć to słowo, pech chciał, że do gry zgłosili się kiedyś studenci MIMUW, pierwsze ich pytanie brzmiało: "czy to słowo to żaba?" przeciwnicy odetchnęli z ulgą, najwyraźniej jacyś mocno nieogarnięci przyszli - pomyśleli i odpowiedzieli, że nie, po tym dzielni studenci otworzyli słownik w środku i zadali pytanie: "czy to słowo jest w słowniku przed czy po X", gdzie X to słowo znajdujące się w okolicy połowy słownika, po odpowiedzi wiedzieli już w której części słownika należy szukać słowa, robiąc tak dalej odgadli słowo bez problemu<br /> <br /> ==== Problem skoczka ====<br /> Mamy szachownicę n na n pól i pytanie: czy jest możliwe aby skoczek odwiedził wszystkie pola dokładnie raz? rozwiązanie brutalne wymaga dodatkowej tablicy n x n w której będziemy zaznaczać czy odwiedziliśmy już dane pole czy nie i sprawdzenia wszystkich możliwości<br /> <br /> <br /> <br /> == Złożoność pamięciowa ==<br /> <br /> Złożoność pamięciową mierzymy w liczbie komórek pamięci komputera zajmowanych przez program. Tu znów dla uproszczenia będziemy się skupiać na tym ile zajmują "właściwe" dane, na których program wykonuje operacje oraz -- żeby uniknąć problemów związanych z typami i reprezentacją liczba -- dla uproszczenia zakładamy, że jedna liczba / komórka tablicy / innej struktury zajmuje jedną "jednostkę". (Chyba że w zadaniu jest explicite powiedziane, że jest inaczej.)<br /> Także omówiony wyżej program, który ma znajdywać maximum w tablicy N elementowej będzie miał złożoność pamięciową O(N).<br /> <br /> <br /> === Przykłady: ===<br /> <br /> ==== Ciekawostka -- oszczędzanie na każdej zmiennej ====<br /> <br /> Napisz program, który zamieni wartościami zmienne a i b. Tzn jeśli na początku a = 1, b = 2, to wynikiem działania programu ma być a = 2, b = 1.<br /> <source lang="python"><br /> c = a<br /> a = b<br /> b = c<br /> </source><br /> <br /> Potrzebujemy aż 3 komórek pamięci. Czy da się oszczędniej?<br /> <source lang="python"><br /> a = a + b <br /> b = a - b <br /> a = a - b<br /> </source><br /> <br /> ==== Sortowanie przez zliczanie: ====<br /> <br /> Mamy tablicę t, N liczb naturalnych do posortowania. Poznaliśmy już kilka algorytmów, które nam pozwolą ją posortować w czasię O(N^2).<br /> Teraz załóżmy, że mamy dodatkową informację o tych liczbach -- są one z zakresu 1 do M. Możemy zastosować taki trick:<br /> * alokujemy tablicę pom, długości M, wypełnioną zerami.<br /> * przechodzimy tablicę t, i wykonujemy operację pom[t[i]] += 1<br /> * teraz wystarczy przejść raz tablicę pom, i utworzyć tablicę która ma na pierwszych pom[1] miejscach jedynki, pom[2] miejscach dwójki, itd, która będzie naszym wynikiem<br /> <br /> <br /> * Jaki wpływ ma ten trick na złożoność obliczeniową, a jaki na pamięciową sortowania?<br /> <br /> <br /> W przypadku gdy na przykład M = O(NlogN) poprawia to złożoność czasową algorytmu, natomista pogarsza złożoność pamięciową. <br /> <br /> <br /> * Cobędzie, gdy M << N?<br /> <br /> Załóżmy teraz, że M << N. Wtedy takie sortowanie poprawia złożoność czasową nie pogarszając pamięciowej O(M + N).<br /> <br /> <br /> * Załóżmy, że tym razem jednak interesuje nas zachowanie pierwotnej kolejności tych liczb. To znaczy dwie liczby "3" traktujemy jako w pewien sposób różne, i mają pozostać względem siebie w pierwotnej kolejności ("stabilność" sortowania). Czyli liczby są pewnego rodzaju obiektami. Zaalokujmy zatem w tablicy pom tablice, w których będizemy przechowywać obiekty, w takiej kolejności, w jakiej je spotkamy, a już nie tylko ilość ich wystąpień. <br /> Jaka będzie w tej sytuacji złożoność pamięciowa i obliczeniowa?<br /> <br /> Złożoność czasowa pozostaje taka sama, natomiast złożoność pamięciowa zwiększa się do O(M * N).<br /> <br /> <br /> Jakie złożoności pamięciowe mają poznane algorytmy sortowania:<br /> <br /> * bąbelkowe (przykład wyżej)<br /> * przez wstawianie (przykad wyżej)<br /> * selection sort (przez wybór za każdym razem najmniejszego elementu i wstawienie go w odpowiednie miejsce)<br /> <br /> <br /> == Koszt zamortyzowany ==<br /> <br /> Czasami w praktyce dana operacja "na ogół" będize miała koszt 1, ale w najgorszym przypadku może mieć koszt O(N). Jednak wiemy, że zdarzy się to raz na N przypadków, i wiemy to w sposób deterministyczny. Wtedy ten koszt O(N) rozłoży się równomienie na te N przypadków, co spowoduje, że każdą operację będizemy mogli traktować jakby miała koszt O(2), w każdym razie stały. Mówimy wtedy o koszcie zamortyzowanym.<br /> <br /> Dobrym przykładem jest tablica dynamiczna, jej implementacja polega na tym, że początkowo bierzemy tablicę pewnej długości na przykład 2, wstawiamy do niej elementy (w czasie stałym), a gdy pojemność tablicy się kończy to alokujemy nową dwukrotnie większą i tu musimy przepisać wszystkie elementy (w czasie liniowym), zatem wkładając n elementów mamy 2 + 4 + 8 + ... + floor(lg(n)) + n = 2(floor(lg(n)) - 1) + n przypisań przy n operacjach, zatem koszt zamortyzowany to 1 + 1 / n + 2(floor(lg(n)) - 1)<br /> <br /> </div>

Jarekz