Déterminer la complexité des fonctions récursives (notation Big O)

J'ai un Computer Science Midterm demain et j'ai besoin d'aide pour déterminer la complexité de ces fonctions récursives. Je sais comment résoudre des cas simples, mais j'essaie toujours d'apprendre à résoudre ces cas plus difficiles. Ce ne sont que quelques-uns des exemples de problèmes que je n'ai pas pu comprendre. Toute aide serait très appréciée et aiderait grandement dans mes études, merci!

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

La complexité temporelle, en notation Big O, pour chaque fonction, est dans l'ordre numérique:

1. La première fonction est appelée récursivement n fois avant d'atteindre le cas de base de sorte que son O(n), souvent appelé linéaire .
2. La deuxième fonction est appelée n-5 à chaque fois, nous en déduisons donc cinq avant d'appeler la fonction, mais n-5 l'est aussi O(n). (Appelé en fait n / 5 fois. Et, O (n / 5) = O (n)).
3. Cette fonction est log (n) base 5, pour chaque fois que nous divisons par 5 avant d'appeler la fonction, sa O(log(n))(base 5), souvent appelée logarithmique et le plus souvent la notation Big O et l'analyse de complexité utilisent la base 2.
4. Dans le quatrième, c'est O(2^n), ou exponentiel , puisque chaque appel de fonction s'appelle deux fois sauf s'il a été récursé n fois.

5. Comme pour la dernière fonction, la boucle for prend n / 2 puisque nous augmentons de 2, et la récursion prend n-5 et puisque la boucle for est appelée récursivement donc la complexité temporelle est en (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2- 10n, en raison du comportement asymptotique et des considérations du pire scénario ou de la limite supérieure que le grand O cherche, nous ne sommes intéressés que par le plus grand terme O(n^2).

   Bonne chance à mi-parcours;)

Pour le cas où n <= 0, T(n) = O(1). Par conséquent, la complexité temporelle dépendra du moment n >= 0.

Nous examinerons le cas n >= 0dans la partie ci-dessous.

1.

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

où a est une constante.

Par induction:

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

où a, b sont des constantes.

2.

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

où a est une constante

Par induction:

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

où a, b sont des constantes et k <= 0

3.

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

où a est une constante

Par induction:

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

où a, b sont des constantes

4.

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

où a est une constante

Par induction:

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)

où a, b sont des constantes.

5.

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

où n est une constante

Réécrire n = 5q + roù q et r sont des nombres entiers et r = 0, 1, 2, 3, 4

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

Nous avons q = (n - r) / 5, et puisque r <5, nous pouvons le considérer comme une constante, doncq = O(n)

Par induction:

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)

Puisque r <4, nous pouvons trouver une constante b de sorte que 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)

L'un des meilleurs moyens que je trouve pour approximer la complexité de l'algorithme récursif est de dessiner l'arbre de récursivité. Une fois que vous avez l'arborescence récursive:

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

1. La première fonction aura la longueur net le nombre de nœuds feuilles, 1donc la complexité seran*1 = n

2. La deuxième fonction aura à nouveau la longueur n/5et le nombre de nœuds feuilles, de 1sorte que la complexité sera n/5 * 1 = n/5. Il devrait être approximé àn

3. Pour la troisième fonction, étant donné qu'elle nest divisée par 5 à chaque appel récursif, la longueur de l'arbre récursif sera log(n)(base 5)et le nombre de nœuds foliaires à nouveau 1 donc la complexité seralog(n)(base 5) * 1 = log(n)(base 5)

4. Pour la quatrième fonction, puisque chaque nœud aura deux nœuds enfants, le nombre de nœuds feuilles sera égal à (2^n)et la longueur de l'arbre récursif sera ntelle que la complexité sera (2^n) * n. Mais comme il nest insignifiant devant (2^n), il peut être ignoré et la complexité ne peut qu’être dite (2^n).

5. Pour la cinquième fonction, deux éléments introduisent la complexité. Complexité introduite par la nature récursive de la fonction et complexité introduite par la forboucle dans chaque fonction. En faisant le calcul ci-dessus, la complexité introduite par la nature récursive de la fonction sera ~ net la complexité due à la boucle n. La complexité totale sera n*n.

Remarque: Il s'agit d'un moyen rapide et sale de calculer la complexité (rien d'officiel!). J'adorerais entendre des commentaires à ce sujet. Merci.

Nous pouvons le prouver mathématiquement, ce qui me manquait dans les réponses ci-dessus.

Il peut considérablement vous aider à comprendre comment calculer n'importe quelle méthode. Je recommande de le lire de haut en bas pour bien comprendre comment le faire:

1. T(n) = T(n-1) + 1Cela signifie que le temps qu'il faut pour que la méthode se termine est égal à la même méthode mais avec n-1 qui est T(n-1)et nous ajoutons maintenant + 1parce que c'est le temps qu'il faut pour que les opérations générales soient terminées (sauf T(n-1)). Maintenant, nous allons trouver T(n-1)comme suit: T(n-1) = T(n-1-1) + 1. Il semble que nous pouvons maintenant former une fonction qui peut nous donner une sorte de répétition afin que nous puissions comprendre pleinement. Nous allons placer le côté droit de la T(n-1) = ...place de l' T(n-1)intérieur de la méthode T(n) = ...qui nous donnera: T(n) = T(n-1-1) + 1 + 1qui est - T(n) = T(n-2) + 2à - dire que nous devons trouver notre manque k: T(n) = T(n-k) + k. L'étape suivante consiste à prendre n-ket à affirmer que, n-k = 1car à la fin de la récursivité, il faudra exactement O (1) lorsquen<=0. De cette simple équation, nous le savons maintenant k = n - 1. Mettons kdans notre méthode finale: T(n) = T(n-k) + kqui nous donnera: T(n) = 1 + n - 1qui est exactement nou O(n).
2. Est le même que 1. Vous pouvez le tester vous-même et voir que vous obtenez O(n).
3. T(n) = T(n/5) + 1comme précédemment, le temps de fin de cette méthode est égal au temps de la même méthode, mais n/5c'est pourquoi elle est limitée T(n/5). Trouvons T(n/5)comme en 1: T(n/5) = T(n/5/5) + 1qui est T(n/5) = T(n/5^2) + 1. Place Let T(n/5)intérieur T(n)pour le calcul final: T(n) = T(n/5^k) + k. Encore une fois comme précédemment, n/5^k = 1qui est n = 5^kexactement comme demander ce qui au pouvoir de 5, nous donnera n, la réponse est log5n = k(log de base 5). Plaçons nos conclusions T(n) = T(n/5^k) + kcomme suit: T(n) = 1 + lognqui estO(logn)
4. T(n) = 2T(n-1) + 1ce que nous avons ici est fondamentalement le même qu'avant mais cette fois nous invoquons la méthode récursivement 2 fois donc nous la multiplions par 2. Voyons ce T(n-1) = 2T(n-1-1) + 1qui est T(n-1) = 2T(n-2) + 1. Notre prochain endroit comme avant, plaçons notre conclusion: T(n) = 2(2T(n-2)) + 1 + 1qui T(n) = 2^2T(n-2) + 2nous donne T(n) = 2^kT(n-k) + k. Trouvons ken revendiquant ce n-k = 1qui est k = n - 1. Mettons kcomme suit: T(n) = 2^(n-1) + n - 1ce qui est à peu prèsO(2^n)
5. T(n) = T(n-5) + n + 1C'est presque la même chose que 4 mais maintenant nous ajoutons nparce que nous avons une forboucle. Trouvons T(n-5) = T(n-5-5) + n + 1lequel est T(n-5) = T(n - 2*5) + n + 1. Mettons-le: T(n) = T(n-2*5) + n + n + 1 + 1)qui est T(n) = T(n-2*5) + 2n + 2)et pour le k: T(n) = T(n-k*5) + kn + k)encore: n-5k = 1qui n = 5k + 1est à peu près n = k. Cela nous donnera: T(n) = T(0) + n^2 + nce qui est à peu près O(n^2).

Je recommande maintenant de lire le reste des réponses qui, maintenant, vous donneront une meilleure perspective. Bonne chance pour gagner ces gros O :)

La clé ici est de visualiser l'arborescence des appels. Une fois cela fait, la complexité est:

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

ce dernier terme peut être calculé de la même manière que pour une fonction itérative normale.

Au lieu de cela, le nombre total de nœuds d'une arborescence complète est calculé comme

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

Où C est le nombre d'enfants de chaque nœud et L est le nombre de niveaux de l'arbre (racine incluse).

Il est facile de visualiser l'arbre. Commencez par le premier appel (nœud racine) puis dessinez un nombre d'enfants identique au nombre d'appels récursifs dans la fonction. Il est également utile d'écrire le paramètre passé au sous-appel comme "valeur du nœud".

Donc, dans les exemples ci-dessus:

1. l'arbre d'appel ici est C = 1, L = n + 1. La complexité du reste de la fonction est O (1). La complexité totale est donc 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. l'arbre d'appel ici est C = 1, L = n / 5. La complexité du reste de la fonction est O (1). La complexité totale est donc L * O (1) = (n / 5) * O (1) = O (n)

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

3. l'arbre d'appel ici est C = 1, L = log (n). La complexité du reste de la fonction est O (1). La complexité totale est donc 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. l'arbre d'appel ici est C = 2, L = n. La complexité du reste de la fonction est O (1). Cette fois, nous utilisons la formule complète pour le nombre de nœuds dans l'arborescence d'appels car C> 1. Par conséquent, la complexité totale est (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. l'arbre d'appel ici est C = 1, L = n / 5. La complexité du reste de la fonction est O (n). La complexité totale est donc L * O (1) = (n / 5) * O (n) = O (n ^ 2)

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