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

Question

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

Mam jutro egzamin z informatyki 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 były tylko niektóre z przykładowych problemów, których nie mogłem rozgryźć. Każda pomoc będzie bardzo mile widziana i bardzo pomoże w moich badaniach, 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);
}

161

complexity-theory big-o recursion

Author: Tot Zam, 2012-11-20

Source

3 answers

W przypadku, gdy n <= 0, T(n) = O(1). Dlatego złożoność czasu będzie zależeć od kiedy n >= 0.

Rozważymy przypadek n >= 0 w 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 to jakieś stałe.

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ą stałymi i k

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ą jakąś stałą

4.

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

Gdzie a jest jakąś stałą

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 to jakieś stałe.

5.

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

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

Write n = 5m - b (m, b are integer; b = 0, 1, 2, 3, 4), m = (n + b) / 5:

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

(właściwie, aby być bardziej rygorystycznym tutaj, nowa funkcja T'(n) powinna być zdefiniowane tak, że T'(5r - q) = T(5r) gdzie q = 0, 1, 2, 3, 4. Wiemy 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 tak, że T'(n) <= a * f(n) + b, możemy wywnioskować, że T(n) <= a * f(n) + b i stąd T(n) jest w O(f). Ten krok nie jest naprawdę konieczny, ale łatwiej jest myśleć, gdy nie masz do czynienia z resztą.)

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

102

Author: nhahtdh,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-11-20 07:55:00

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

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

Pierwsza funkcja będzie miała długość n i liczbę węzłów liścia 1 więc złożoność będzie n*1 = n
Druga funkcja będzie miała długość n/5 i liczbę węzłów liścia ponownie 1 więc złożoność będzie n/5 * 1 = n/5. Powinno być przybliżone do n
Dla trzeciego funkcja, ponieważ {[1] } jest dzielona przez 5 przy każdym wywołaniu rekurencyjnym, długość drzewa rekurencyjnego 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)
Dla czwartej funkcji, ponieważ każdy węzeł będzie miał dwa węzły potomne, Liczba węzłów liścia będzie równa (2^n), a długość drzewa rekurencyjnego będzie n, więc złożoność będzie wynosić (2^n) * n. Ale ponieważ {[1] } jest nieistotna przed (2^n), można ją zignorować, a złożoność można tylko powiedzieć, że jest (2^n).
Dla piątej funkcji istnieją dwa elementy wprowadzające złożoność. Złożoność wprowadzana przez rekurencyjną naturę funkcji i złożoność wprowadzana przez pętlę for w każdej funkcji. Wykonując powyższe obliczenia, złożoność wprowadzoną przez rekurencyjną naturę funkcji będzie ~ n, a złożoność spowodowana pętlą 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 oficjalnie!). Chciałbym usłyszeć opinie na ten temat. Dzięki.

12

Author: Shubham,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-03-01 00:39:25

score 207 · Accepted Answer

Złożoność czasu, w notacji Big O, dla każdej funkcji, jest w porządku liczbowym:

pierwsza funkcja jest wywoływana rekurencyjnie N razy przed osiągnięciem przypadku podstawowego, więc jej O(n), często nazywanaliniową .
druga funkcja nazywa się n-5 za każdym razem, więc odliczamy pięć od N przed wywołaniem funkcji, ale n-5 jest również O(n). (Właściwie nazywa się kolejność n / 5 razy. I, O(N / 5) = O (n) ).
Ta funkcja jest log(n) baza 5, za każdym razem dzielimy przez 5 przed wywołaniem funkcji tak jej O(log(n)) (baza 5), często nazywana logarytmiczna i najczęściej notacja Big O i analiza złożoności wykorzystuje bazę 2.
w czwartym jest O(2^n) lub wykładniczy, ponieważ każde wywołanie funkcji wywołuje się dwa razy, chyba że zostało rekurencyjnie 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 nazywa się rekurencyjnie dlatego złożoność czasowa jest w (n-5) *(n/2) = (2N-10) * N = 2N^2-10n, ze względu na asymptotyczne zachowanie i rozważania najgorszego scenariusza lub górną granicę, do której dąży Wielkie O, interesuje nas tylko największy termin tak O(n^2).

Powodzenia na egzaminach;)