[[
✎ pl:dydaktyka:asd:cwiczenia:2011-compl
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== Złożoność algorytmów ====== **Termin zajęć:** 29/30.03.2011 **Do przygotowania:** - Znajomość i rozumienie pojęć: - Złożoność obliczeniowa. - Złożoność pamięciowa: - Działanie algorytmów "w miejscu". - Złożoność pesymistyczna. - Złożoność oczekiwana. - Złożoność optymistyczna. **Zajęcia odbywać się będą głownie przy tablicy**. Nie ma konieczności przynoszenia laptopów. ---- === Metoda rekurencji uniwersalnej === Umożliwia szybkie wyznaczanie rozwiązania równania rekurencyjnego postaci: \\ <latex>T(n) = aT(n/b)+f(n)</latex> gdzie: * <latex>a \geq 1</latex> * f(n) jest funkcją asymptotycznie dodatnią. * iloraz <latex>n/b</latex> interpretujemy jako <latex>\lceil n/b \rceil</latex> lub jako <latex>\lfloor n/b \rfloor</latex> Wtedy **T(n)** może być ograniczona asymptotycznie w następujący sposób: - Jeżeli <latex>f(n) = \Theta(n^{\log_{b}(a)-\epsilon})</latex> dla pewnej stałej ε > 0 to, <latex>T(n) = \Theta(n^{\log_{b}(a)})</latex> - Jeśli <latex>f(n) = O(n^{\log_{b}(a)})</latex> to, <latex>T(n) = \Theta(n^{\log_{b}(a)}\lg(n))</latex> - Jeżeli <latex>f(n) = \Omega(n^{\log_{b}(a)+\epsilon})</latex> dla pewnej stałej ε > 0 oraz <latex> af(n/b) \leq cf(n)</latex> dla pewnej stałej **c** i wszystkich dostatecznie dużych **n**, to <latex>T(n) = \Theta(f(n))</latex> === Zadania === - Metodą reukrencji uniwersalnej wyznacz złożoność obliczeniową algorytmu wyszukiwania binarnego. - Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(n-1) + \lfloor \log(n) \rfloor</latex> - Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(n/4) + T(3n/4) + n</latex> - Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(\lfloor\sqrt{n}\rfloor) + \lfloor\sqrt{n}\rfloor</latex>
pl/dydaktyka/asd/cwiczenia/2011-compl.1301667628.txt.gz
· ostatnio zmienione: 2019/06/27 15:51 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry