Określanie złożoności dla funkcji rekursywnych (notacja Big O)

Question

Mam jutro naukę w zakresie informatyki i potrzebuję pomocy w określeniu złożoności tych funkcji rekursywnych. Wiem, jak rozwiązywać proste przypadki, ale nadal próbuję nauczyć się rozwiązywać te trudniejsze sprawy. To tylko kilka przykładów problemów, których nie mogłem wymyślić. Każda pomoc byłaby bardzo cenna 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); 
} 

Answer 1

Złożony czas, w notacji Big O, dla każdej funkcji, jest w porządku liczbowym:

1. Pierwsza funkcja jest wywoływana rekurencyjnie n razy przed osiągnięciem przypadku podstawy tak jej O(n) często nazywany liniowy.
2. Druga funkcja jest nazywana n-5 dla każdego czasu, więc odejmujemy pięć od n przed wywołaniem funkcji, ale n-5 jest również O(n). (Rzeczywiście nazywany porządkiem n/5 razy, a O (n/5) = O (n)).
3. Ta funkcja jest log (n) podstawa 5, za każdym razem dzielimy przez 5 przed wywołaniem funkcji, więc jego O(log(n)) (podstawy 5), często nazywany logarytmiczna i najczęściej asymptotyczne tempo wzrostu i analiza złożoności wykorzystuje bazę 2 .
4. w czwartym, to O(2^n) lub wykładniczy, ponieważ każde wywołanie funkcji nazywa się dwa razy, chyba że zostało recursed n razy.

5. Jeśli chodzi o ostatnią funkcję, pętla for przyjmuje n/2, ponieważ zwiększamy o 2, a rekursja ma wartość n-5, a ponieważ pętla for nazywa się rekurencyjnie, dlatego złożoność czasu jest w (n -5) * (n/2) = (2n-10) * n = 2n^2- 10n, ze względu na zachowania asymptotyczne i najgorsze scenariusze lub górną granicę, o którą walczy O, interesuje nas tylko największy termin, więc O(n^2).

   Powodzenia w midterms;)

Answer 2

Dla przypadku, gdy n <= 0, T(n) = O(1). W związku z tym złożoność czasu zależy od tego, kiedy n >= 0.

Rozpatrzymy sprawę n >= 0 w części poniżej.

1.

T(n) = a + T(n - 1) 

gdzie pewne stałe.

przez indukcję:

T(n) = n * a + T(0) = n * a + b = O(n) 

gdzie a, b są niektóre stałe.

2.

T(n) = a + T(n - 5) 

gdzie pewne stałe

przez indukcję:

T(n) = ceil(n/5) * a + T(k) = ceil(n/5) * a + b = O(n) 

gdzie a, b są niektóre stałe i k < = 0

3.

T(n) = a + T(n/5) 

gdzie a jest jakieś c Sta ła

przez indukcję:

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n) 

gdzie a, b są niektóre stałe

4.

T(n) = a + 2 * T(n - 1) 

gdzie pewne stałe

przez indukcję:

T(n) = a + 2a + 4a + ... + 2^n * a + T(0) * 2^n 
    = a * 2^(n+1) - a + b * 2^n 
    = (2 * a + b) * 2^n - a 
    = O(2^n) 

gdzie a, b są pewne stałe.

5.

T(n) = n/2 + T(n - 5) 

można udowodnić przez indukcję, że T(5k) >= T(5k - d) gdzie d = 0, 1, 2, 3, 4

zapisu n = 5m - b (m, b oznacza liczbę całkowitą, b = 0, 1 , 2, 3, 4), a następnie m = (n + b)/5:

T(n) = T(5m - b) <= T(5m) 

(rzeczywistości, być bardziej rygorystyczne tu nowa funkcja T'(n) powinna być określona w taki sposób, T'(5r - q) = T(5r) gdzie q = 0, 1, 2, 3, 4. Znamy T(n) <= T'(n), jak udowodniono powyżej. Kiedy wiemy, że T'(n) jest w O(f), co oznacza, że ​​istnieje stała a, b, więc T'(n) <= a * f(n) + b, możemy wywnioskować, że T(n) <= a * f(n) + b, a tym samym T(n) jest w O(f). Ten krok nie jest to naprawdę konieczne, ale łatwiej jest myśleć, kiedy nie mamy do czynienia z resztą)

Rozszerzanie T(5m).

T(5m) = 5m/2 + T(5m - 5) 
     = (5m/2 + 5/2) * m/2 + T(0) 
     = O(m^2) = O(n^2) 

Dlatego T(n) jest O(n^2).

Answer 3

Jednym z najlepszych sposobów na przybliżenie złożoności algorytmu rekursywnego jest rysowanie drzewa rekursji.Gdy masz rekurencyjnej drzewa:

Complexity = length of tree from root node to leaf node * number of leaf nodes 

1. Pierwsza funkcja będzie miała długość n i ilość liści węzła 1 więc złożoność będzie n*1 = n

2. Druga funkcja będzie miał długość n/5 i liczby węzłów liści ponownie 1, więc złożoność będzie n/5 * 1 = n/5. Powinna ona być zbliżona do n

3. Do trzeciej funkcji, ponieważ n jest podzielona przez 5 na każde wywołanie rekurencyjne, długość rekurencyjnego drzewa będzie log(n)(base 5), a liczba węzłów liściowych ponownie 1 więc złożoność będzie log(n)(base 5) * 1 = log(n)(base 5)

4. Dla czwartej funkcji, ponieważ każdy węzeł ma dwa węzły potomne, liczba węzłów liści będzie równa (2^n), a długość drzewa rekurencyjnego będzie wynosić n, więc złożoność będzie (2^n) * n. Ale od n jest nieznaczna przed (2^n), można go zignorować i złożoność można powiedzieć tylko (2^n).

5. Dla piątej funkcji istnieją dwa elementy wprowadzające złożoność. Złożoność wprowadzona przez rekursywny charakter funkcji i złożoności wprowadzona przez pętlę for w każdej funkcji. Wykonując powyższe obliczenia, złożoność wprowadzona przez rekursywny charakter funkcji będzie wynosić ~ n, a złożoność z powodu pętli for n. Całkowita złożoność będzie wynosić n*n.

Uwaga: Jest to szybki i brudny sposób obliczania złożoności (nic oficjalnego!). Chciałbym usłyszeć opinie na ten temat. Dzięki.