Mam jutro informatykę i potrzebuję pomocy w określeniu złożoności tych funkcji rekurencyjnych. Wiem, jak rozwiązywać proste sprawy, ale wciąż staram się nauczyć, jak rozwiązywać te trudniejsze sprawy. To tylko kilka przykładowych problemów, których nie mogłem zrozumieć. Każda pomoc byłaby bardzo mile widziana i bardzo pomogłaby w moich studiach, dziękuję!
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
recursion
big-o
complexity-theory
Michael_19
źródło
źródło
Odpowiedzi:
Złożoność czasowa, w zapisie Big O, dla każdej funkcji, jest uporządkowana numerycznie:
O(n)
często nazywana liniową .O(n)
. (Faktycznie nazywany porządkiem n / 5 razy. I, O (n / 5) = O (n)).O(log(n))
(podstawa 5), często nazywana logarytmiczną, a najczęściej notacja i analiza złożoności Big O używa podstawy 2.O(2^n)
, czy wykładniczy , ponieważ każde wywołanie funkcji nazywa się dwa razy, chyba że zostało recursed n razy.Jeśli chodzi o ostatnią funkcję, pętla for przyjmuje n / 2, ponieważ zwiększamy o 2, a rekurencja przyjmuje n-5, a ponieważ pętla for jest wywoływana rekurencyjnie, dlatego złożoność czasowa wynosi (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2- 10n, ze względu na zachowanie asymptotyczne i względy najgorszego scenariusza lub górną granicę, do której dąży duże O, interesuje nas tylko największy termin tak
O(n^2)
.Powodzenia w śródterminach;)
źródło
n/2
iteracjefor
pętli, dlaczego zmniejszenie o 5 nie spowodujen/5
wywołań rekurencyjnych? Nadal by to skutkowało,O(n^2)
ale wydaje się bardziej intuicyjnym wyjaśnieniem. Po co mieszać odejmowanie i dzielenie, gdy są niezbędne, by robić to samo?n/5
nien-5
. I ostatecznie całość sprowadza się doO(N^2)
.W przypadku, gdzie
n <= 0
,T(n) = O(1)
. Dlatego złożoność czasu zależy od tego, kiedyn >= 0
.Sprawę rozpatrzymy
n >= 0
w części poniżej.1.
gdzie a jest jakąś stałą.
Przez indukcję:
gdzie a, b są pewnymi stałymi.
2)
gdzie a jest jakąś stałą
Przez indukcję:
gdzie a, b są pewnymi stałymi, a k <= 0
3)
gdzie a jest jakąś stałą
Przez indukcję:
gdzie a, b są pewnymi stałymi
4
gdzie a jest jakąś stałą
Przez indukcję:
gdzie a, b są pewnymi stałymi.
5
gdzie n jest jakąś stałą
Przepisz,
n = 5q + r
gdzie q i r są liczbami całkowitymi, a r = 0, 1, 2, 3, 4Mamy
q = (n - r) / 5
, a ponieważ r <5, możemy uznać to za stałe, więcq = O(n)
Przez indukcję:
Ponieważ r <4, możemy znaleźć pewną stałą b, aby
b >= T(r)
źródło
Jednym z najlepszych sposobów na przybliżenie złożoności algorytmu rekurencyjnego jest narysowanie drzewa rekurencji. Po utworzeniu drzewa rekurencyjnego:
n
i liczbę węzłów liścia,1
więc złożoność będzien*1 = n
Druga funkcja będzie miała ponownie długość
n/5
i liczbę węzłów liści,1
więc złożoność będzien/5 * 1 = n/5
. Powinno to być przybliżone don
W przypadku trzeciej funkcji, ponieważ
n
jest dzielona przez 5 przy każdym wywołaniu rekurencyjnym, długość drzewa rekurencyjnego będzie wynosićlog(n)(base 5)
, a liczba węzłów liści ponownie 1, więc złożoność będzielog(n)(base 5) * 1 = log(n)(base 5)
W przypadku czwartej funkcji, ponieważ każdy węzeł będzie miał dwa węzły potomne, liczba węzłów liściowych będzie równa,
(2^n)
a długość drzewa rekurencyjnego będzien
tak złożona(2^n) * n
. Ponieważ jednakn
jest mało znaczący(2^n)
, można go zignorować, a złożoność można jedynie powiedzieć(2^n)
.W przypadku piątej funkcji istnieją dwa elementy wprowadzające złożoność. Złożoność wprowadzona przez rekurencyjny charakter funkcji i złożoność wprowadzona przez
for
pętlę w każdej funkcji. Wykonując powyższe obliczenia, złożoność wprowadzona przez rekurencyjną naturę funkcji będzie,~ n
a złożoność wynika z pętli forn
. Całkowita złożoność będzien*n
.Uwaga: Jest to szybki i brudny sposób obliczania złożoności (nic oficjalnego!). Bardzo chciałbym usłyszeć opinie na ten temat. Dzięki.
źródło
2^n
wysokości drzewan
, to nielog n
. Wysokość byłaby tylko,log n
gdybyn
reprezentowała całkowitą liczbę węzłów w drzewie. Ale tak nie jest.Możemy to udowodnić matematycznie, czego mi brakowało w powyższych odpowiedziach.
Może to znacznie pomóc zrozumieć, jak obliczyć dowolną metodę. Zalecam przeczytanie go od góry do dołu, aby w pełni zrozumieć, jak to zrobić:
T(n) = T(n-1) + 1
Oznacza to, że czas potrzebny na zakończenie metody jest równy tej samej metodzie, ale z n-1, który jestT(n-1)
i teraz dodajemy,+ 1
ponieważ jest to czas potrzebny na zakończenie ogólnych operacji (opróczT(n-1)
). Teraz mamy zamiar znaleźćT(n-1)
sposób następujący:T(n-1) = T(n-1-1) + 1
. Wygląda na to, że możemy teraz utworzyć funkcję, która może dać nam jakieś powtórzenie, abyśmy mogli w pełni zrozumieć. Będziemy umieszczać po prawej stronieT(n-1) = ...
zamiastT(n-1)
wewnątrz metodyT(n) = ...
, które dadzą nam:T(n) = T(n-1-1) + 1 + 1
co jestT(n) = T(n-2) + 2
lub innymi słowy musimy znaleźć nasz brakującyk
:T(n) = T(n-k) + k
. Następnym krokiem jest zrobienie tegon-k
i twierdzenie,n-k = 1
że pod koniec rekurencji zajmie to dokładnie O (1) kiedyn<=0
. Z tego prostego równania wiemy to terazk = n - 1
. Umieśćmyk
w naszej ostatecznej metodzie:T(n) = T(n-k) + k
która da nam:T(n) = 1 + n - 1
która jest dokładnien
lubO(n)
.O(n)
.T(n) = T(n/5) + 1
tak jak poprzednio, czas zakończenia tej metody jest równy czasowi tej samej metody, ale zn/5
tym jest związanyT(n/5)
. ZnajdźmyT(n/5)
jak w 1:T(n/5) = T(n/5/5) + 1
który jestT(n/5) = T(n/5^2) + 1
. Miejsce ChodźmyT(n/5)
do środkaT(n)
do ostatecznego obliczenia:T(n) = T(n/5^k) + k
. Ponownie, jak poprzednio,n/5^k = 1
co jestn = 5^k
dokładnie tak samo, jak pytanie, co przy sile 5, da nam n, odpowiedź brzmilog5n = k
(log podstawy 5). Umieśćmy nasze ustalenia wT(n) = T(n/5^k) + k
następujący sposób:T(n) = 1 + logn
który jestO(logn)
T(n) = 2T(n-1) + 1
to, co mamy tutaj, jest w zasadzie takie samo jak poprzednio, ale tym razem wywołujemy metodę rekurencyjnie 2 razy, więc mnożymy ją przez 2. Przekonajmy się,T(n-1) = 2T(n-1-1) + 1
która jestT(n-1) = 2T(n-2) + 1
. Nasze następne miejsce jak poprzednio, umieśćmy nasze znalezisko:T(n) = 2(2T(n-2)) + 1 + 1
coT(n) = 2^2T(n-2) + 2
nam dajeT(n) = 2^kT(n-k) + k
. Przekonajmy się,k
twierdząc, żen-k = 1
jestk = n - 1
. Umieśćmy wk
następujący sposób: zT(n) = 2^(n-1) + n - 1
grubszaO(2^n)
T(n) = T(n-5) + n + 1
Jest prawie taki sam jak 4, ale teraz dodajemy,n
ponieważ mamy jednąfor
pętlę. Sprawdźmy,T(n-5) = T(n-5-5) + n + 1
który jestT(n-5) = T(n - 2*5) + n + 1
. Umieśćmy to:T(n) = T(n-2*5) + n + n + 1 + 1)
co jestT(n) = T(n-2*5) + 2n + 2)
i dla k:T(n) = T(n-k*5) + kn + k)
znowu:n-5k = 1
co ton = 5k + 1
jest z grubszan = k
. To da nam: zT(n) = T(0) + n^2 + n
grubszaO(n^2)
.Polecam teraz przeczytać resztę odpowiedzi, które teraz zapewnią lepszą perspektywę. Powodzenia w wygrywaniu tych wielkich O :)
źródło
Kluczem tutaj jest wizualizacja drzewa połączeń. Po wykonaniu tej czynności złożoność jest następująca:
ten drugi termin można obliczyć w ten sam sposób, jak w przypadku normalnej funkcji iteracyjnej.
Zamiast tego obliczane są całkowite węzły pełnego drzewa jako
Gdzie C to liczba potomków każdego węzła, a L to liczba poziomów drzewa (łącznie z korzeniem).
Łatwo jest zwizualizować drzewo. Zacznij od pierwszego wywołania (węzeł główny), a następnie narysuj liczbę dzieci taką samą, jak liczba wywołań rekurencyjnych w funkcji. Przydatne jest również zapisanie parametru przekazanego do wezwania podrzędnego jako „wartość węzła”.
W powyższych przykładach:
źródło