[Algorytmy][Teoria złożoności] Równości i kolejność funkcji

[Chungu]

Witam.
Uczę się na własną rękę algorytmów i mam sporo problemów. Czy mógłby mi ktoś opisać sposób rozwiązania poniżej zamieszczonych zadań lub wręcz je rozwiązać żebym mógł, wzorując się na tym rozwiązywać kolejne?
Oto zadania:

Zad 2. Zbadaj, która z równości jest prawdziwa:
a)\(\displaystyle{ 2^{n+1} =O \left( 2^{n} \right)}\)
d)\(\displaystyle{ n^{3}+6n+1=O \left( n^{6} \right)}\)
Zad 2.2 Udowodnij, stosując metodę niezmienników pętli, że wartością zmiennej result, po wykonaniu następującego algorytmu w strukturze liczb rzeczywistych jest n!:

Kod: Zaznacz cały

 {i;=2;result:=1;while(i<n+1)do result;=result x i;i:=i+1;od;}

Zad 5 (tutaj tylko pytanko czy dobrze uporządkowałem)
Uporządkuj, ze względu na rosnący rząd następujące funkcje:
\(\displaystyle{ \lg \ n!, \ 2^{3\lg n}, \ n ^{2}, \ 2^{\lg n}, \ n!, \ \log n}\)

Odpowiedź(moja):\(\displaystyle{ \log \ n , \ 2^{\lg n}, \ , n^{2}, \ 2^{3 \lg n} , \lg \ n!, \ n!}\)

Dziękuję.

[Igor V]

Zad 2
Generalnie masz trzy sposoby na udowodnienie że \(\displaystyle{ f(n) = O(g(n))}\) :
- z definicji (co akurat tutaj jest proste)
- z własności notacji \(\displaystyle{ O}\)
- z sprawdzenia zbieżności granicy \(\displaystyle{ \lim_{n \to \infty} \left| \frac{f(n)}{g(n)}\right|}\)

Najłatwiej jest zrobić trzecim sposobem

Zad 2.2
Narzuca się że nie zmiennikiem jest \(\displaystyle{ result := (i-1)!}\)
Przed wejściem do pętli działa, działa także po każdym obrocie, a po wyjściu z pętli mamy :
\(\displaystyle{ result := n!}\)

PS : A nie w strukturze liczb naturalnych ?

Zad 5
Wklep w wolframa i zobacz jak rosną funkcje względem siebie.

[Afish]

Odpowiedź(moja):\(\displaystyle{ \log \ n , \ 2^{\lg n}, \ , n^{2}, \ 2^{3 \lg n} , \lg \ n!, \ n!}\)

Dziękuję.

\(\displaystyle{ \lg n!}\) można łatwo uprościć i wtedy widać, że jest źle. \(\displaystyle{ 2^{3 \lg n}}\) też jest niepoprawnie.

[Chungu]

Ten dowód zadania 2 z granicą to będzie, że jak ta granica będzie większa lub równa 0 to równość jest spełniona?