Złożoność obliczeniowa algorytmów

Odpowiedz Nowy wątek
2016-06-02 20:04
0

Witam wszytstkich forumowiczów
z góry przepraszam za założenie tego tematu, ale szukam pomocy i wg mnie tutaj biorąc pod uwagę potencjał forumowiczów znajdę pomoc na moje pytania. Jestem zielony ze złożoności algorytmów. Bardzo prosiłbym o pomoc w tych zadaniach , o napisanie łopatologicznie jak to należy robić- policzyć(te zadania).

Zad.1 Roważ algorytm o złożoności obliczeniowej O(N do 2) . Jak wpłynie na czas obliczeń dwukrotne zmniejszenie rozmiaru problemu oraz w algorytmie o złożoności obliczeniowej O (n!) jak wpłynie na czas obliczeń zwiększenie problemu z 10 do 30.

Zad.2 Czas rozwiązania problemu (w ns) wyrqza sie funkcja f(n) gdzie n jest rozmiarem problemu. Nalezy oszacowac czas obliczen problemu o rozmiarze 10 do 6 dla nastepujacych funkcji żlozonosciowych : nlgn, n do potegi 4, 2 do potegi n).

Dziękuję za pomoc

edytowany 1x, ostatnio: jur3ck, 2016-06-02 20:05

Pozostało 580 znaków

2016-06-02 20:22
0

Skoro masz algorytm O(n2) to znaczy że dla problemu o rozmiarze n = k czas wykonania będzie wynosił n2 = k2 a teraz podstawiasz za n wartość n = k/2 to masz teraz n2 = (k/2)2 = k2/4
Wynika z tego że czas wykonania zmalał 4 razy.
Analogicznie jak wyżej skoro było O(n!) to czas wykonania był 10! a teraz dla n = 30 masz n! = 30! czyli czas wykonania wzrośnie 30!/10! razy

Zadanie 2 analogicznie.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2016-06-24 01:18

Pozostało 580 znaków

2016-06-02 20:24
0

Ale jaki tu jest problem? Do odpowiedzi na to pytanie nawet nie trzeba za bardzo wiedzieć, co to złożoność obliczeniowa. Więc tak:
Zad.1. Zapisz sobie złożoność tego pierwszego algorytmu jako c*n^2, gdzie c-stała. Sprawdź co się stanie, jak zamiast n wstawisz 2n. Voila. Tak samo drugi podpunkt
Zad.2. Może warto rozważyć podstawienie do tych wzorów n=10^6?

Pozostało 580 znaków

2016-06-05 10:31
0

Ok, dzięki czyli w tym rozmiarze problemu 106 dla funkcji n4, będę miał 10^24 to będzie w jednostkach czasu (ns)? Dobrze rozumiem?

Mam jeszcze pytanie jak rozwiązać taką rekurencję
T(n)=4T(n/4)+n
T(1)=0

tam nie powinna być czasem wartość całkowita z n/4, czyli [n/4]? Edit. W ogóle dziwny ten zwór, bo jak niby policzyć T(2)? - gepir 2016-06-05 12:14

Pozostało 580 znaków

2016-06-05 11:59
0

Przez indukcje nie wiem jak ale wyjdzie log4(n) lub n log4(n) w zalezności czy ta rekurencja tylko liczy wartość funkcji, czy przedstawia koszty wykonania pod kroku:P

edytowany 1x, ostatnio: topik92, 2016-06-05 12:00

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0