Określ thetę, Omegę oraz O następujących funkcji:
f(n) = 2n^2 + 3n + 2nlog_2n
g(n) = f(n) + O(n^3)
h(n) = f(n) + g(n)
Moje rozwiązanie:
f(n) = O(n^2)
g(n) = O(n^3)
h(n) = O(n^3)
f(n) = theta(n^2)
theta dla g, h nie da się określić
f(n) = Omega(n^2)
Jak określić Omega dla g, h?
Przepraszam za brak LaTeXa!
Omega dla g będzie taka jak Omega dla f bo g na pewno będzie działać nie szybciej niż f
Omega dla h będzie taka sama jak dla f i dla g (w rzeczywistości jak większe z Omega(f) i Omega(g)) bo h na pewno będzie działać nie szybciej niż niż wolniejsza z f i g
Brzmi logicznie :)
No ale co jeśli...
g(n) = 2n^2 + 3n + 2nlog_2n -0n^3 -2n^2 -3n -2nlog_2n
?
Nie rozumiem za bardzo twojego zapisu. Nie odejmuje się asymptotycznej złożoności obliczeniowej...
Hmm... może za bardzo matematycznie podchodzę do tego :p
g(n) to konkretna funkcja? Jeśli tak, to dodajmy do funkcji f funkcję o złożoności co najwyżej O(n^3) postaci:
-2n^2 -3n -2nlog_2n.
Czy te współczynniki mogą być ujemne?
Wówczas mamy g(n) = 0. Co źle rozumiem? :)
Czy może komputer tak po prostu nie działa i najpierw musi wynokać tych f(n) operacji, a potem dopiero kolejne?
Sumarycznie nie mogą ci z tego wychodzić ujemne liczby. Rząd złożoności obliczeniowej mówi ci o tym jak zmienia sie czas wykonania algorytmu w zalezności od zmiany rozmiaru problemu wejściowego. Poza jakimiś wydumanymi dziwnymi przypadkami raczej nie ma takiej możliwości żeby czas algorutmu malał w odpowiedzi na większe dane wejsciowe, ale tak czy siak czas wykonania algorytmu ujemny być nie może więc nie ma takiej możliwości żeby złączenie dwóch algorytmów w sekwencyjny sposób spowodowało przyspieszenie tego pierwszego algorytmu (bo ten drugi miał "ujemny" czas wykonania ;) ) Mówie oczywiście o teorii obliczeń! Bo w praktyce takie cuda jak branch prediction i cache mogą zdziałać cuda :P
Jeśli masz złożoność O(n^2) to znaczy ze zmiana danych wejściowych dwukrotnie spowoduje spowolnienie algorytmu 4 krotnie, jeśli O(n) to 2 krotnie,