[Teoria złożoności] Udowodnij złożoności

[leszczu450]

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).

[bartek118]

1. Jest OK.
2. Zupełnie analogicznie jak 1 - pokaż próby
3. Wykorzystaj fakt, że \(\displaystyle{ |a_k n^k | \leq n^{k+1}}\) dla odpowiednio dużych \(\displaystyle{ n}\).

[leszczu450]

Rozwiązanie podpunktu (b) dla \(\displaystyle{ \Gamma= \mathcal{O}}\) :

Wiemy, że zachodzą następujące nierówności:


\(\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)|}\)

oraz:

\(\displaystyle{ h=\mathcal{O}(r)}\). Oznacza to, że \(\displaystyle{ \exists_{c_2 >0 , c_2 \in \RR} \quad \exists_{n_0 \in \NN} \quad |h(n)| \le c_2 |r(n)|}\)

Zauważmy , że:

\(\displaystyle{ |(f \cdot h)(n)|= |f(n)| \cdot |h(n)| \le c_1 c_2 |g(n)| \cdot |r(n)|= c_3 |(g \cdot r)(n)| \square}\)

Analogicznie wygląda to dla Omegi, tyle że zamieniamy nierówności . Dla Thety szacowanie z obu stron, również pełna analogia. Mam pytanie jeszcze o \(\displaystyle{ n_0}\) . Nie biore przypadkiem minimum zawsze z tych dwóch warunków ?-- 18 sty 2014, o 00:55 --Co do podpunktu (c) to wpadłem na taki pomysł. Popraw mnie jeśli się mylę.

\(\displaystyle{ f(n)=a_0 + a_1 n + a_2 n^2 + \ldots + a_d n^d}\)

Celem jest ograniczenie \(\displaystyle{ |f(n)|}\) z góry i z dołu czymś rzędu \(\displaystyle{ n^d}\). Proponuje:

\(\displaystyle{ |C_2 \cdot n^d|=|\min\left\{ a_0, \ldots a_d\right\}n^d|\le |f(n)| \le |(a_0 + \ldots + a_d)n^d|= |C_1 \cdot n^d|}\)

Co kończy dowód.

[bartek118]

Wszystko super. Co do tych \(\displaystyle{ n_0}\) - bierzemy maksimum z obu definicji.

[leszczu450]

bartek118, dzięki wielkie !