Bepalen van complexiteit voor recursieve functies (Big O-notatie)

Ik heb morgen een Computer Science Midterm en ik heb hulp nodig bij het bepalen van de complexiteit van deze recursieve functies. Ik weet hoe ik eenvoudige gevallen moet oplossen, maar ik probeer nog steeds te leren hoe ik deze moeilijkere gevallen moet oplossen. Dit waren slechts enkele van de voorbeeldproblemen die ik niet kon achterhalen. Alle hulp wordt zeer op prijs gesteld en zou enorm helpen bij mijn studie, bedankt!

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

Antwoord 1, autoriteit 100%

De tijdscomplexiteit, in Big O-notatie, voor elke functie:

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

Deze functie wordt n keer recursief aangeroepen voordat het basisgeval wordt bereikt, dus O(n), vaak lineair genoemd.

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

Deze functie wordt voor elke keer n-5 genoemd, dus we trekken vijf af van n voordat we de functie aanroepen, maar n-5 is ook O(n).
(Eigenlijk de orde van n/5 keer genoemd. En, O(n/5) = O(n)).

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

Deze functie is log(n) grondtal 5, voor elke keer dat we delen door 5
voordat de functie wordt aangeroepen, zodat de O(log(n))(basis 5), vaak logaritmisch genoemd, en meestal gebruikt de Big O-notatie en complexiteitsanalyse basis 2.

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

Hier is het O(2^n), of exponentieel, aangezien elke functieaanroep zichzelf twee keer aanroept, tenzij het herhaald is n keer.

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

En hier neemt de for-lus n/2 omdat we met 2 toenemen, en de recursie duurt n/5 en aangezien de for-lus recursief wordt genoemd, is de complexiteit van de tijd dus binnen

(n/5) * (n/2) = n^2/10,

vanwege asymptotisch gedrag en worst-case scenario-overwegingen of de bovengrens waar grote O naar streeft, zijn we alleen geïnteresseerd in de grootste term, dus O(n^2).

Veel succes met je tussentijdse examens 😉

Antwoord 2, autoriteit 31%

Voor het geval n <= 0, T(n) = O(1). Daarom zal de tijdscomplexiteit afhangen van wanneer n >= 0.

We zullen het geval n >= 0 in het onderstaande gedeelte beschouwen.

1.

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

waarbij a een constante is.

Door inductie:

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

waarbij a, b een constante zijn.

2.

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

waarbij a een constante is

Door inductie:

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

waarbij a, b een constante zijn en k <= 0

3.

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

waarbij a een constante is

Door inductie:

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

waarbij a, b een constante zijn

4.

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

waarbij a een constante is

Door inductie:

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)

waarbij a, b een constante zijn.

5.

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

waarbij n een constante is

Herschrijf n = 5q + r waarbij q en r geheel getal zijn en r = 0, 1, 2, 3, 4

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

We hebben q = (n - r) / 5, en aangezien r < 5, we kunnen het als een constante beschouwen, dus q = O(n)

Door inductie:

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)

Sinds r < 4, kunnen we een constante b vinden zodat 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)

Antwoord 3, autoriteit 8%

Een van de beste manieren die ik vind om de complexiteit van het recursieve algoritme te benaderen, is het tekenen van de recursieboom. Zodra je de recursieve boom hebt:

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

1. De eerste functie heeft een lengte van n en het aantal bladknooppunten 1, dus de complexiteit is n*1 = n

2. De tweede functie zal de lengte hebben van n/5 en het aantal bladknooppunten opnieuw 1 dus de complexiteit zal n/5 * 1 = n/5. Het moet worden geschat op n

3. Voor de derde functie, aangezien n bij elke recursieve aanroep door 5 wordt gedeeld, is de lengte van de recursieve boom log(n)(base 5), en het aantal bladknooppunten opnieuw 1 dus de complexiteit is log(n)(base 5) * 1 = log(n)(base 5)

4. Voor de vierde functie, aangezien elk knooppunt twee onderliggende knooppunten heeft, is het aantal bladknooppunten gelijk aan (2^n) en is de lengte van de recursieve boom n dus complexiteit zal (2^n) * n zijn. Maar aangezien n onbeduidend is vóór (2^n), kan het worden genegeerd en kan complexiteit alleen worden gezegd als (2^n).

5. Voor de vijfde functie zijn er twee elementen die de complexiteit introduceren. Complexiteit geïntroduceerd door recursieve aard van functie en complexiteit geïntroduceerd door for lus in elke functie. Door de bovenstaande berekening uit te voeren, zal de complexiteit die wordt geïntroduceerd door de recursieve aard van de functie ~ n zijn en de complexiteit als gevolg van for loop n. De totale complexiteit is n*n.

Opmerking: dit is een snelle en vuile manier om complexiteit te berekenen (niets officieels!). Hoor hier graag feedback over. Bedankt.

Antwoord 4, autoriteit 3%

We kunnen het wiskundig bewijzen, iets wat ik in de bovenstaande antwoorden miste.

Het kan u dramatisch helpen begrijpen hoe u een methode kunt berekenen.
Ik raad aan om het van boven naar beneden te lezen om volledig te begrijpen hoe je het moet doen:

1. T(n) = T(n-1) + 1 Het betekent dat de tijd die nodig is om de methode te voltooien gelijk is aan dezelfde methode, maar met n-1 die T(n-1) en we voegen nu + 1 toe omdat dit de tijd is die nodig is om de algemene bewerkingen te voltooien (behalve T(n-1)).
   Nu gaan we T(n-1) als volgt vinden: T(n-1) = T(n-1-1) + 1. Het lijkt erop dat we nu een functie kunnen vormen die ons een soort herhaling kan geven, zodat we het volledig kunnen begrijpen. We plaatsen de rechterkant van T(n-1) = ... in plaats van T(n-1) in de methode T(n) = ... wat ons zal geven: T(n) = T(n-1-1) + 1 + 1 wat T(n) = T(n-2) + 2 of met andere woorden we moeten onze ontbrekende k vinden: T(n) = T(n-k) + k. De volgende stap is om n-k te nemen en te beweren dat n-k = 1 omdat aan het einde van de recursie precies O(1) nodig is als n<=0. Uit deze eenvoudige vergelijking weten we nu dat k = n - 1. Laten we k in onze laatste methode plaatsen: T(n) = T(n-k) + k wat ons zal geven: T(n) = 1 + n - 1 wat precies n of O(n) is.
2. Is hetzelfde als 1. Je kunt het zelf testen en zien dat je O(n) krijgt.
3. T(n) = T(n/5) + 1 zoals eerder, de tijd die deze methode nodig heeft om te eindigen is gelijk aan de tijd van dezelfde methode maar met n/5 daarom is het gebonden aan T(n/5). Laten we T(n/5) zoeken zoals in 1: T(n/5) = T(n/5/5) + 1 wat T(n/5) = T(n/5^2) + 1.
   Laten we T(n/5) in T(n) plaatsen voor de uiteindelijke berekening: T(n) = T(n/5^k) + k. Nogmaals zoals eerder, n/5^k = 1 wat n = 5^k is, wat precies hetzelfde is als vragen wat in de macht van 5, ons n geeft, het antwoord is log5n = k (log van grondtal 5). Laten we onze bevindingen als volgt in T(n) = T(n/5^k) + k plaatsen: T(n) = 1 + logn wat O(logn)
4. T(n) = 2T(n-1) + 1 wat we hier hebben is in principe hetzelfde als voorheen, maar deze keer roepen we de methode recursief 2 keer aan, dus vermenigvuldigen we deze met 2 Laten we T(n-1) = 2T(n-1-1) + 1 zoeken, dat is T(n-1) = 2T(n-2) + 1. Onze volgende plaats als voorheen, laten we onze bevinding plaatsen: T(n) = 2(2T(n-2)) + 1 + 1 wat T(n) = 2^2T(n-2) + 2 dat geeft ons T(n) = 2^kT(n-k) + k. Laten we k vinden door te beweren dat n-k = 1 wat k = n - 1 is. Laten we k als volgt plaatsen: T(n) = 2^(n-1) + n - 1 wat ongeveer O(2^n)
5. T(n) = T(n-5) + n + 1 Het is bijna hetzelfde als 4 maar nu voegen we n toe omdat we er één hebben for lus. Laten we T(n-5) = T(n-5-5) + n + 1 zoeken, dat is T(n-5) = T(n - 2*5) + n + 1. Laten we het plaatsen: T(n) = T(n-2*5) + n + n + 1 + 1) wat T(n) = T(n-2*5) + 2n + 2) en voor de k: T(n) = T(n-k*5) + kn + k) nogmaals: n-5k = 1 dat is n = 5k + 1 dat is ongeveer n = k. Dit geeft ons: T(n) = T(0) + n^2 + n wat ongeveer O(n^2) is.

Ik raad u nu aan de rest van de antwoorden te lezen, die u nu een beter perspectief zullen geven.
Veel succes met het winnen van die grote O’s 🙂

Antwoord 5

De sleutel hier is om de gespreksboom te visualiseren. Als je dat eenmaal hebt gedaan, is de complexiteit:

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

de laatste term kan op dezelfde manier worden berekend als voor een normale iteratieve functie.

In plaats daarvan worden de totale knooppunten van een volledige boom berekend als

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

Waarbij C het aantal onderliggende punten van elk knooppunt is en L het aantal niveaus van de boom (inclusief root).

Het is gemakkelijk om de boom te visualiseren. Begin bij de eerste aanroep (rootknooppunt) en teken vervolgens een aantal kinderen hetzelfde als het aantal recursieve aanroepen in de functie. Het is ook handig om de parameter die aan de sub-aanroep is doorgegeven te schrijven als “waarde van het knooppunt”.

Dus, in de bovenstaande voorbeelden:

1. de oproepboom hier is C = 1, L = n+1. Complexiteit van de rest van de functie is O(1). Daarom is de totale complexiteit 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. aanroepboom hier is C = 1, L = n/5. Complexiteit van de rest van de functie is O(1). Daarom is de totale complexiteit L * O(1) = (n/5) * O(1) = O(n)

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

3. aanroepboom hier is C = 1, L = log(n). Complexiteit van de rest van de functie is O(1). Daarom is de totale complexiteit 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. aanroepboom hier is C = 2, L = n. Complexiteit van de rest van de functie is O(1).
   Deze keer gebruiken we de volledige formule voor het aantal knooppunten in de oproepboom omdat C > 1. De totale complexiteit is dus (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. aanroepboom hier is C = 1, L = n/5. Complexiteit van de rest van de functie is O(n). Daarom is de totale complexiteit L * O(1) = (n/5) * O(n) = O(n^2)

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

Antwoord 6

Ik zie dat voor het geaccepteerde antwoord (recursivefn5), sommige mensen problemen hebben met de uitleg. dus ik zou proberen om het naar mijn beste weten te verduidelijken.

1. De for-lus wordt n/2 keer uitgevoerd omdat we bij elke iteratie i (de teller) met een factor 2 verhogen. Dus zeg n = 10, de for-lus loopt 10/2 = 5 keer dwz wanneer i respectievelijk 0,2,4,6 en 8 is.

2. In hetzelfde opzicht wordt de recursieve aanroep met een factor 5 verminderd voor elke keer dat hij wordt aangeroepen, d.w.z. hij wordt n/5 keer uitgevoerd. Neem opnieuw aan dat n = 10, de recursieve oproep wordt uitgevoerd voor 10/5 = 2 keer, d.w.z. wanneer n 10 en 5 is en dan raakt het het basisgeval en eindigt.

3. Als we de totale looptijd berekenen, wordt de for-lus n/2 keer uitgevoerd voor elke keer dat we de recursieve functie aanroepen. aangezien de recursieve fxn n/5 keer wordt uitgevoerd (in 2 hierboven), loopt de for-lus voor (n/2) * (n/5) = (n^2)/10 keer, wat zich vertaalt naar een algemene Big O-runtime van O(n^2) – de constante negeren (1/10)…