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

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);
}

Złożoność czasowa, w zapisie Big O, dla każdej funkcji, jest uporządkowana numerycznie:

1. Pierwsza funkcja jest wywoływana rekurencyjnie n razy przed osiągnięciem przypadku podstawowego, więc jest O(n)często nazywana liniową .
2. Druga funkcja nazywa się n-5 za każdym razem, więc odejmujemy pięć od n przed wywołaniem funkcji, ale n-5 również O(n). (Faktycznie nazywany porządkiem n / 5 razy. I, O (n / 5) = O (n)).
3. Ta funkcja to log (n) podstawa 5, za każdym razem, gdy dzielimy przez 5 przed wywołaniem funkcji, więc jej 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.
4. W czwartym, jest to O(2^n), czy 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 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;)

W przypadku, gdzie n <= 0, T(n) = O(1). Dlatego złożoność czasu zależy od tego, kiedy n >= 0.

Sprawę rozpatrzymy n >= 0w części poniżej.

1.

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

gdzie a jest jakąś stałą.

Przez indukcję:

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

gdzie a, b są pewnymi stałymi.

2)

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

gdzie a jest jakąś stałą

Przez indukcję:

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

gdzie a, b są pewnymi stałymi, a k <= 0

3)

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

gdzie a jest jakąś stałą

Przez indukcję:

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

gdzie a, b są pewnymi stałymi

4

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

gdzie a jest jakąś stałą

Przez indukcję:

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

gdzie a, b są pewnymi stałymi.

5

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

gdzie n jest jakąś stałą

Przepisz, n = 5q + rgdzie q i r są liczbami całkowitymi, a r = 0, 1, 2, 3, 4

T(5q + r) = (5q + r) / 2 + T(5 * (q - 1) + r)

Mamy q = (n - r) / 5, a ponieważ r <5, możemy uznać to za stałe, więcq = O(n)

Przez indukcję:

T(n) = T(5q + r)
     = (5q + r) / 2 + (5 * (q - 1) + r) / 2 + ... + r / 2 +  T(r)
     = 5 / 2 * (q + (q - 1) + ... + 1) +  1 / 2 * (q + 1) * r + T(r)
     = 5 / 4 * (q + 1) * q + 1 / 2 * (q + 1) * r + T(r)
     = 5 / 4 * q^2 + 5 / 4 * q + 1 / 2 * q * r + 1 / 2 * r + T(r)

Ponieważ r <4, możemy znaleźć pewną stałą b, aby b >= T(r)

T(n) = T(5q + r)
     = 5 / 2 * q^2 + (5 / 4 + 1 / 2 * r) * q + 1 / 2 * r + b
     = 5 / 2 * O(n ^ 2) + (5 / 4 + 1 / 2 * r) * O(n) + 1 / 2 * r + b
     = O(n ^ 2)

Jednym z najlepszych sposobów na przybliżenie złożoności algorytmu rekurencyjnego jest narysowanie drzewa rekurencji. Po utworzeniu drzewa rekurencyjnego:

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

1. Pierwsza funkcja będzie miała długość ni liczbę węzłów liścia, 1więc złożoność będzien*1 = n

2. Druga funkcja będzie miała ponownie długość n/5i liczbę węzłów liści, 1więc złożoność będzie n/5 * 1 = n/5. Powinno to być przybliżone don

3. W przypadku trzeciej funkcji, ponieważ njest 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)

4. 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ędzie ntak złożona (2^n) * n. Ponieważ jednak njest mało znaczący (2^n), można go zignorować, a złożoność można jedynie powiedzieć (2^n).

5. 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 forpętlę w każdej funkcji. Wykonując powyższe obliczenia, złożoność wprowadzona przez rekurencyjną naturę funkcji będzie, ~ na złożoność wynika z pętli for n. Całkowita złożoność będzie n*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.

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ć:

1. T(n) = T(n-1) + 1Oznacza to, że czas potrzebny na zakończenie metody jest równy tej samej metodzie, ale z n-1, który jest T(n-1)i teraz dodajemy, + 1ponieważ jest to czas potrzebny na zakończenie ogólnych operacji (oprócz T(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 stronie T(n-1) = ...zamiast T(n-1)wewnątrz metody T(n) = ..., które dadzą nam: T(n) = T(n-1-1) + 1 + 1co jest T(n) = T(n-2) + 2lub innymi słowy musimy znaleźć nasz brakujący k: T(n) = T(n-k) + k. Następnym krokiem jest zrobienie tego n-ki twierdzenie, n-k = 1że pod koniec rekurencji zajmie to dokładnie O (1) kiedyn<=0. Z tego prostego równania wiemy to teraz k = n - 1. Umieśćmy kw naszej ostatecznej metodzie: T(n) = T(n-k) + kktóra da nam: T(n) = 1 + n - 1która jest dokładnie nlub O(n).
2. To to samo, co 1. Możesz to przetestować samodzielnie i przekonać się, że otrzymujesz O(n).
3. T(n) = T(n/5) + 1tak jak poprzednio, czas zakończenia tej metody jest równy czasowi tej samej metody, ale z n/5tym jest związany T(n/5). Znajdźmy T(n/5)jak w 1: T(n/5) = T(n/5/5) + 1który jest T(n/5) = T(n/5^2) + 1. Miejsce Chodźmy T(n/5)do środka T(n)do ostatecznego obliczenia: T(n) = T(n/5^k) + k. Ponownie, jak poprzednio, n/5^k = 1co jest n = 5^kdokładnie tak samo, jak pytanie, co przy sile 5, da nam n, odpowiedź brzmi log5n = k(log podstawy 5). Umieśćmy nasze ustalenia w T(n) = T(n/5^k) + knastępujący sposób: T(n) = 1 + lognktóry jestO(logn)
4. T(n) = 2T(n-1) + 1to, 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) + 1która jest T(n-1) = 2T(n-2) + 1. Nasze następne miejsce jak poprzednio, umieśćmy nasze znalezisko: T(n) = 2(2T(n-2)) + 1 + 1co T(n) = 2^2T(n-2) + 2nam daje T(n) = 2^kT(n-k) + k. Przekonajmy się, ktwierdząc, że n-k = 1jest k = n - 1. Umieśćmy w knastępujący sposób: z T(n) = 2^(n-1) + n - 1grubszaO(2^n)
5. T(n) = T(n-5) + n + 1Jest prawie taki sam jak 4, ale teraz dodajemy, nponieważ mamy jedną forpętlę. Sprawdźmy, T(n-5) = T(n-5-5) + n + 1który jest T(n-5) = T(n - 2*5) + n + 1. Umieśćmy to: T(n) = T(n-2*5) + n + n + 1 + 1)co jest T(n) = T(n-2*5) + 2n + 2)i dla k: T(n) = T(n-k*5) + kn + k)znowu: n-5k = 1co to n = 5k + 1jest z grubsza n = k. To da nam: z T(n) = T(0) + n^2 + ngrubsza O(n^2).

Polecam teraz przeczytać resztę odpowiedzi, które teraz zapewnią lepszą perspektywę. Powodzenia w wygrywaniu tych wielkich O :)

Kluczem tutaj jest wizualizacja drzewa połączeń. Po wykonaniu tej czynności złożoność jest następująca:

nodes of the call tree * complexity of other code in the function

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

                  C^L - 1
                  -------  , when C>1
               /   C - 1
              /
 # of nodes =
              \    
               \ 
                  L        , when C=1

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:

1. drzewko wywołań to C = 1, L = n + 1. Złożoność reszty funkcji wynosi O (1). Dlatego całkowita złożoność wynosi L * O (1) = (n + 1) * O (1) = O (n)

n     level 1
n-1   level 2
n-2   level 3
n-3   level 4
... ~ n levels -> L = n

2. drzewko wywołań to C = 1, L = n / 5. Złożoność reszty funkcji wynosi O (1). Dlatego całkowita złożoność wynosi L * O (1) = (n / 5) * O (1) = O (n)

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5

3. drzewko wywołań to C = 1, L = log (n). Złożoność reszty funkcji wynosi O (1). Dlatego całkowita złożoność wynosi L * O (1) = log5 (n) * O (1) = O (log (n))

n
n/5
n/5^2
n/5^3
... ~ log5(n) levels -> L = log5(n)

4. drzewko wywołania tutaj to C = 2, L = n. Złożoność reszty funkcji wynosi O (1). Tym razem używamy pełnej formuły dla liczby węzłów w drzewie wywołań, ponieważ C> 1. Dlatego całkowita złożoność wynosi (C ^ L-1) / (C-1) * O (1) = (2 ^ n - 1 ) * O (1) = O (2 ^ n) .

               n                   level 1
      n-1             n-1          level 2
  n-2     n-2     n-2     n-2      ...
n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3    ...     
              ...                ~ n levels -> L = n

5. drzewko wywołań to C = 1, L = n / 5. Złożoność reszty funkcji wynosi O (n). Dlatego całkowita złożoność wynosi L * O (1) = (n / 5) * O (n) = O (n ^ 2)

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5