Uszereguj funkcje złożoności obliczeniowej alg

thomas_

Uszereguj funkcje złożoności obliczeniowej alg

Post autor: thomas_ » 6 wrz 2011, o 15:58

1. Uszereguj rosnąco funkcje złożoności obliczeniowej algorytmu: \(\displaystyle{ O(n), O(n^2), O(\log \log n ), O(1), O(2^n), O( \log ^ 2(n)), O(n^n), O( \sqrt{n}).}\)
2. Stosując technikę programowania dynamicznego wyznacz minimalną liczbę elementarnych mnożeń łańcucha macierzy \(\displaystyle{ A\ B \ C\ D}\) posiadających odpowiednio wymiary \(\displaystyle{ 2x_5, 5x_1, 1x_4, 4x_2}\).

Proszę o rozwiązanie i krótkie wyjaśnienie.
Ostatnio zmieniony 6 wrz 2011, o 17:12 przez ares41, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

Uszereguj funkcje złożoności obliczeniowej alg

Post autor: adambak » 6 wrz 2011, o 17:10

szeregujemy, patrząc która jest asymptotycznie większa:
\(\displaystyle{ O(1)<O(\log \log n)<O(\log^{2} n)<O( \sqrt{n} )<O(n)<O(n^2)<O(2^n)<O(n^n)}\)

thomas_

Uszereguj funkcje złożoności obliczeniowej alg

Post autor: thomas_ » 6 wrz 2011, o 17:20

a tak bardziej po polskiemu? ;p jestem zielony jeśli o to chodzi.

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

Uszereguj funkcje złożoności obliczeniowej alg

Post autor: adambak » 6 wrz 2011, o 17:26

hmm.. no po paru latach to robi się już automatycznie, więc sorry jeśli za szybko

ale szczerze to nie wiem jak to zrobić, żeby się nie narobić, a dobrze zrobić, spróbujmy:

O\(\displaystyle{ (1)}\) - oznacza czas stały, więc najmniejsza asymptotycznie złożoność, to jest fakt..
resztę funkcji porównujesz, która jest większa asymptotycznie, a więc intuicyjnie definiując która dla odpowiednio dużych \(\displaystyle{ n}\) osiąga większe wartości.. w ten sposób porównujesz funkcje, a bardziej formalnie to badasz granicę:

\(\displaystyle{ \lim_{n \to +\infty} \frac{f(n)}{g(n)}}\)

jeśli wynosi ona nieskończoność (czyli nie istnieje) to znaczy że \(\displaystyle{ f(n)}\) jest asymptotycznie większa od \(\displaystyle{ g(n)}\), jeśli wynosi ona zero to na odwrót..

-- 6 wrz 2011, o 18:27 --

ale tak porównywać to musisz tylko kiedy masz wątpliwości, i to będzie matematycznie super.. w innych przypadkach chyba widać że np \(\displaystyle{ O( \sqrt{n} )<O(n^2)}\)..

thomas_

Uszereguj funkcje złożoności obliczeniowej alg

Post autor: thomas_ » 6 wrz 2011, o 17:36

już mniej więcej chyba wiem o co chodzi.
generalnie chyba podstawiam do każdego po kilka liczb i obserwuje jak rosną te funkcje i porządkuje je, dobrze rozumiem?

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

Uszereguj funkcje złożoności obliczeniowej alg

Post autor: adambak » 6 wrz 2011, o 17:43

bardzo brzydko matematycznie (ale ciii.. spoko nie dziwię Ci się bo niektóre granice są trudne do policzenia ), jednak zadziała jak dobrze podstawisz.. czasem może nie zadziałać, bo np \(\displaystyle{ f(n)=n^n}\) jest większa od \(\displaystyle{ g(n)=2^n}\), dopiero od pewnej wartości, wcześniej jest mniejsza.. jednak jak podstawisz odpowiednio duże \(\displaystyle{ n}\) to wyjdzie na jaw która "większa w nieskończoności"..

thomas_

Uszereguj funkcje złożoności obliczeniowej alg

Post autor: thomas_ » 6 wrz 2011, o 17:51

wielkie dzięki za pomoc.

ODPOWIEDZ