[Teoria złożoności] Sprawdzenie hipotezy
: 18 mar 2017, o 11:54
Zadanie jest nastepujace
Czy dla kazdej funkcji \(\displaystyle{ f(n):N \rightarrow R}\), jezeli
\(\displaystyle{ f(n)=\Omega(2 ^{ \frac{n}{2} }) O(\log ^{2}n ) O(n ^{ \sqrt{7} })}\) to:
\(\displaystyle{ f(n)=\Omega(3 ^{ \sqrt{n} }) \Omega(n ^{ \frac{5}{2} }) \Omega(100 ^{ \sqrt{n} } )}\)
no i w odpowiedziach mam ze to prawda. Niestety nie moge dojsc dlaczego?
Czy ktos moglby wytlumaczyc mi o co w tym chodzi??
I jeszcze jedno co by bylo gdyby te funkcjie sie dodawaly a nie mnozyly
\(\displaystyle{ f(n)=\Omega(2 ^{ \frac{n}{2} }) +O(\log ^{2}n ) +O(n ^{ \sqrt{7} })}\) to:
\(\displaystyle{ f(n)=\Omega(3 ^{ \sqrt{n} }) +\Omega(n ^{ \frac{5}{2} }) +\Omega(100 ^{ \sqrt{n} } )}\)
Czy dla kazdej funkcji \(\displaystyle{ f(n):N \rightarrow R}\), jezeli
\(\displaystyle{ f(n)=\Omega(2 ^{ \frac{n}{2} }) O(\log ^{2}n ) O(n ^{ \sqrt{7} })}\) to:
\(\displaystyle{ f(n)=\Omega(3 ^{ \sqrt{n} }) \Omega(n ^{ \frac{5}{2} }) \Omega(100 ^{ \sqrt{n} } )}\)
no i w odpowiedziach mam ze to prawda. Niestety nie moge dojsc dlaczego?
Czy ktos moglby wytlumaczyc mi o co w tym chodzi??
I jeszcze jedno co by bylo gdyby te funkcjie sie dodawaly a nie mnozyly
\(\displaystyle{ f(n)=\Omega(2 ^{ \frac{n}{2} }) +O(\log ^{2}n ) +O(n ^{ \sqrt{7} })}\) to:
\(\displaystyle{ f(n)=\Omega(3 ^{ \sqrt{n} }) +\Omega(n ^{ \frac{5}{2} }) +\Omega(100 ^{ \sqrt{n} } )}\)