[[
✎ 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: * a ≥ 1 * b > 1 * 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) = O(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) = \Theta(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> === Niejasności z zajęć === Metoda graficzna: <code> for(i=0;i<n;i++) for(j=0;j<n;j++) OD </code> * i(n)=n * j(i)=n * T(n)=n^2 <code> for(i=0;i<n;i++) for(j=0;j<n;j+=2) OD </code> * i(n)=n * j(i)=n/2 * T(n)=n^2/2 <code> for(i=0;i<n;i+=2) for(j=0;j<i;j++) OD </code> * i(n)=n/2 * j(i)=i * T(n)=n^2/8 <code> for(i=0;i<n;i+=2) for(j=i;j>=1;j/=2) OD </code> * i(n)=n/2 * j(i)=log i * T(n)=n/2(log(n/2) - 1)
pl/dydaktyka/asd/cwiczenia/2011-compl.txt
· ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry