[Teoria złożoności] Udowodnij złożoności
: 17 sty 2014, o 17:09
Cześć !
Mam zadanie, za które niestety nie wiem jak się zabrać i co mam dokładnie zrobić. Brzmi ono następująco:
Niech \(\displaystyle{ \Gamma \in \left\{ \mathcal{O}, \Theta , \Omega\right\}}\) oraz \(\displaystyle{ f,g,h,r : \NN \to \RR}\). Udowodnić, że:
(a) jeśli \(\displaystyle{ f = \Gamma(g)}\) oraz \(\displaystyle{ g=\Gamma(h)}\), to \(\displaystyle{ f=\Gamma(h)}\)
(b) jeśli \(\displaystyle{ f = \Gamma(g)}\) oraz \(\displaystyle{ g=\Gamma(r)}\), to \(\displaystyle{ f \cdot h=\Gamma(g \cdot r)}\)
(c) jeśli \(\displaystyle{ f}\) jest zadana przez wielomian stopnia \(\displaystyle{ d}\), to \(\displaystyle{ f= \Theta(n^d)}\)
Proszę o pomoc w zrozumienie tego zadania i o drobne wskzówki. Wiem co to znaczy, że funkcja \(\displaystyle{ f}\)jest co najmniej, co najwyżej i dokładnie rzędu funkcji \(\displaystyle{ g}\). Potrafię też udowodnić, że \(\displaystyle{ f=\Theta(g) \Leftrightarrow f=\mathcal{O}(g) \wedge f=\Omega(g)}\).
Czy w przykładzie (a) i (b) chodzi o to, że po kolei mam rozwiązać te przykłady podstawiając raz za \(\displaystyle{ \Gamma = \mathcal{O}}\). Potem za Gamme wstawić Omege i zrobić ten przykład dla Omegi i następnie dla Thety ?-- 17 sty 2014, o 20:53 --Udało mi się zrobić podpunkt (a). Założyłem, że zadanie mam wykonać w 3 wersjach.
Żeby ożywić temat, wstawie moje rozwiązanie. Może ktoś się pokusi o ich sprawdzenie. Zaczynam:
Przyjmijmy \(\displaystyle{ \Gamma=\mathcal{O}}\)
Wiemy, że :
1. \(\displaystyle{ f=\mathcal{O}(g)}\). Oznacza to, że \(\displaystyle{ \exists_{c_1 >0 , c_1 \in \RR} \quad \exists_{n_0 \in \NN} \quad |f(n)| \le c_1 |g(n)|}\).
2. \(\displaystyle{ g=\mathcal{O}(h)}\). Oznacza to, że \(\displaystyle{ \exists_{c_2 >0 , c_2 \in \RR} \quad \exists_{n_0 \in \NN} \quad |g(n)| \le c_2 |h(n)|}\).
Zatem: \(\displaystyle{ |f(n)| \le c_1 |g(n)| \le c_1 c_2 |h(n)|}\) Przyjmijmy \(\displaystyle{ c_3 :=c_1c_2}\).
Mamy zatem: \(\displaystyle{ |f(n)| \le c_3|h(n)|}\) . Czyli \(\displaystyle{ f = \mathcal{O}(h) \square}\)
Analogicznie wygląda rozwiązanie podpunktu (a) dla \(\displaystyle{ \Gamma = \Omega}\). Wystarczy zamienić nierówności i wszystko idzie tak jak wyżej. Co do rozwiązania zadania dla \(\displaystyle{ \Gamma= \Theta}\), postępujemy analogicznie, z lekkimi modyfikacjami związanymi z dojściem do tego co cchemy otrzymać. Podpunkt (a) mogę zatem uznać za rozwiązany.
Proszę o sprawdzenie mojego rozumowania i zapisu. Prosze także o wskazówkę do podpunktu (b) i (c).
Mam zadanie, za które niestety nie wiem jak się zabrać i co mam dokładnie zrobić. Brzmi ono następująco:
Niech \(\displaystyle{ \Gamma \in \left\{ \mathcal{O}, \Theta , \Omega\right\}}\) oraz \(\displaystyle{ f,g,h,r : \NN \to \RR}\). Udowodnić, że:
(a) jeśli \(\displaystyle{ f = \Gamma(g)}\) oraz \(\displaystyle{ g=\Gamma(h)}\), to \(\displaystyle{ f=\Gamma(h)}\)
(b) jeśli \(\displaystyle{ f = \Gamma(g)}\) oraz \(\displaystyle{ g=\Gamma(r)}\), to \(\displaystyle{ f \cdot h=\Gamma(g \cdot r)}\)
(c) jeśli \(\displaystyle{ f}\) jest zadana przez wielomian stopnia \(\displaystyle{ d}\), to \(\displaystyle{ f= \Theta(n^d)}\)
Proszę o pomoc w zrozumienie tego zadania i o drobne wskzówki. Wiem co to znaczy, że funkcja \(\displaystyle{ f}\)jest co najmniej, co najwyżej i dokładnie rzędu funkcji \(\displaystyle{ g}\). Potrafię też udowodnić, że \(\displaystyle{ f=\Theta(g) \Leftrightarrow f=\mathcal{O}(g) \wedge f=\Omega(g)}\).
Czy w przykładzie (a) i (b) chodzi o to, że po kolei mam rozwiązać te przykłady podstawiając raz za \(\displaystyle{ \Gamma = \mathcal{O}}\). Potem za Gamme wstawić Omege i zrobić ten przykład dla Omegi i następnie dla Thety ?-- 17 sty 2014, o 20:53 --Udało mi się zrobić podpunkt (a). Założyłem, że zadanie mam wykonać w 3 wersjach.
Żeby ożywić temat, wstawie moje rozwiązanie. Może ktoś się pokusi o ich sprawdzenie. Zaczynam:
Przyjmijmy \(\displaystyle{ \Gamma=\mathcal{O}}\)
Wiemy, że :
1. \(\displaystyle{ f=\mathcal{O}(g)}\). Oznacza to, że \(\displaystyle{ \exists_{c_1 >0 , c_1 \in \RR} \quad \exists_{n_0 \in \NN} \quad |f(n)| \le c_1 |g(n)|}\).
2. \(\displaystyle{ g=\mathcal{O}(h)}\). Oznacza to, że \(\displaystyle{ \exists_{c_2 >0 , c_2 \in \RR} \quad \exists_{n_0 \in \NN} \quad |g(n)| \le c_2 |h(n)|}\).
Zatem: \(\displaystyle{ |f(n)| \le c_1 |g(n)| \le c_1 c_2 |h(n)|}\) Przyjmijmy \(\displaystyle{ c_3 :=c_1c_2}\).
Mamy zatem: \(\displaystyle{ |f(n)| \le c_3|h(n)|}\) . Czyli \(\displaystyle{ f = \mathcal{O}(h) \square}\)
Analogicznie wygląda rozwiązanie podpunktu (a) dla \(\displaystyle{ \Gamma = \Omega}\). Wystarczy zamienić nierówności i wszystko idzie tak jak wyżej. Co do rozwiązania zadania dla \(\displaystyle{ \Gamma= \Theta}\), postępujemy analogicznie, z lekkimi modyfikacjami związanymi z dojściem do tego co cchemy otrzymać. Podpunkt (a) mogę zatem uznać za rozwiązany.
Proszę o sprawdzenie mojego rozumowania i zapisu. Prosze także o wskazówkę do podpunktu (b) i (c).