Cześć,
Czy mógłbym prosić o pomoc w rozwiązaniu zadania, które znajduje się na zdjęcie? Nie wiem jak się za nie zabrać. Próbuje przygotować się do zbliżającego się kolokwium...
0
2
@Althorion: Przecież złożoność drugiego członu jest , mnożymy wszystko przez siebie, i to jest złożóność całości, (większa z sumy).
0
Ok, czyli reasumując wychodziło by takie coś:
Z pierwszego członu O(n^4logn), z drugiego członu O(n^4(logn)^2) . Następnie mnożąc to co znajduje sie w obu członach mam O(n^8(logn)^3) czyli moje F(n) = n^8(logn)^3?
2
patryk2205 napisał(a):
Z pierwszego członu O(n^4logn), z drugiego członu O(n^4(logn)^2) . Następnie mnożąc to co znajduje sie w obu członach mam O(n^8(logn)^3) czyli moje F(n) = n^8(logn)^3?
Dlaczego mnożysz te człony? Przecież w zadaniu są do siebie dodane.
0
A racja... Czyli F(n) to będzie suma członu pierwszego i drugiego?
1
patryk2205 napisał(a):
Ok, czyli reasumując wychodziło by takie coś:
Z pierwszego członu O(n^4logn), z drugiego członu O(n^4(logn)^2) . Następnie mnożąc to co znajduje sie w obu członach mam O(n^8(logn)^3) czyli moje F(n) = n^8(logn)^3?
Nie, następnie dodajesz je do siebie czyli wybierasz większy
0
Większy czyli ten, którego złożoność jest gorsza - czas wykonania zwiększa się szybciej. F(n) = n^4(logn)^2 ?
2
Pozostaje jeszcze jedna kwestia, co mógłbym napisać w uzasadnieniu do tego typu zadania?
Pytania w temacie to jednak lepiej zadawać w postach. No musisz wyciągnąć jakieś wnioski z tego wątku - właściwie sam nasunąłeś sobie uzasadnienie w swoim poprzednim poście, więc wystarczy ubrać ładnie w słowa uzasadniając, co determinuje złożoność obliczeniową całości.
0
Na marginesie, powiem tylko że zadanie nie jest najlepiej opisane. Nie wiadomo jakie jest f(N), można co najwyżej domyślać się jakie jest O(f(N)).