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

267

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);
}
Michael_19
źródło
4
Jeśli nie chcesz za każdym razem przechodzić przez analizę, istnieje technika czarnej skrzynki zwana metodą Master. Ale przy założeniu, że wszystkie rekurencyjne podziały danych wejściowych mają jednakowy rozmiar w każdym przypadku.
Vivek Krishna

Odpowiedzi:

345

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

koder
źródło
masz prawo do piątej, n zmniejszy się dla pętli for, ale dla czwartej nie sądzę, że n ^ 2 jest jak drzewo za każdym razem, gdy wywołujesz rekurencję dwa razy, więc powinno być 2 ^ n plus to było twoje odpowiedz w komentarzu wcześniej.
programista
2
@MJGwater Niech czas działania pętli wynosi m. Kiedy rekurencyjny przebieg 1 raz, wykonanie pętli zajmuje m. Gdy rekurencyjny przebiegnie 2 razy, pętla jest również uruchomiona 2 razy, więc zajmuje 2m ... i tak dalej. Więc to jest „*”, a nie „^”.
bjc
3
@ koder Wyjaśnienie dla 5 wydaje się dziwne. Jeśli zwiększenie o 2 powoduje n/2iteracje forpętli, dlaczego zmniejszenie o 5 nie spowoduje n/5wywoł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?
Jack
1
@coder, więc dla # 4, gdyby w definicji funkcji były 3 wywołania rekurencyjne, miałaby złożoność czasową O (3 ^ n)? A dla 5 połączeń rekurencyjnych byłoby to O (5 ^ n), prawda?
rmutalik
1
@Jack Tak, zastanawiałem się również nad tym samym. Powinno być n/5nie n-5. I ostatecznie całość sprowadza się do O(N^2).
Anuj
128

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)
nhahtdh
źródło
1
Niedawno nie udało mi się odpowiedzieć na pytanie (i rozszerzyć wywiad), które dotyczy analizy czasu i przestrzeni złożoności rekurencyjnej funkcji Fibonacciego. Ta odpowiedź jest epicka i bardzo pomogła. Uwielbiam ją. Chciałbym móc dwukrotnie zagłosować. Wiem, że jest stary, ale czy masz coś podobnego do obliczania miejsca - może link, cokolwiek?
Dimitar Dimitrov
W przypadku numeru 4, mimo że wynik jest taki sam, czy indukcja nie powinna być następująca? T (n) = a + 2T (n-1) = a + 2a + 4T (n-1) = 3a + 4a + 8T (n-1) = a * (2 ^ n - 1) + 2 ^ n * T (0) = a * (2 ^ n - 1) + b * 2 ^ n = (a + b) * 2 ^ n - a = O (2 ^ n)
Snowfish
27

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.

Shubham
źródło
Doskonała odpowiedź! Mam pytanie dotyczące czwartej funkcji. Gdyby miał trzy rekurencyjne wywołania, odpowiedź brzmiałaby (3 ^ n). Czy nadal powiedziałbyś (2 ^ n)?
Ben Forsrup
@Shubham: # 4 wydaje mi się niewłaściwy. Jeśli liczba liści jest równa 2^nwysokości drzewa n, to nie log n. Wysokość byłaby tylko, log ngdyby nreprezentowała całkowitą liczbę węzłów w drzewie. Ale tak nie jest.
Julian A.,
@BenForsrup: Będzie to 3 ^ n, ponieważ każdy węzeł będzie miał trzy węzły potomne. Najlepszym sposobem, aby się tego upewnić, jest narysowanie rekurencyjnego drzewa wartościami obojętnymi.
Shubham
# 2 powinno być n-5 nie n / 5
Fintasys
7

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

OhadM
źródło
1

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
  1. 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
  1. 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)
  1. 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
  1. 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
higlu
źródło