Złożoność obliczeniowa algorytmów

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

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.

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?

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

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

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