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.
Uszereguj funkcje złożoności obliczeniowej alg
Uszereguj funkcje złożoności obliczeniowej alg
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 .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznać się z instrukcją: http://matematyka.pl/latex.htm .
-
- 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
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)}\)
\(\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)}\)
Uszereguj funkcje złożoności obliczeniowej alg
a tak bardziej po polskiemu? ;p jestem zielony jeśli o to chodzi.
-
- 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
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)}\)..
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)}\)..
Uszereguj funkcje złożoności obliczeniowej alg
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?
generalnie chyba podstawiam do każdego po kilka liczb i obserwuje jak rosną te funkcje i porządkuje je, dobrze rozumiem?
-
- 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
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"..