Comment trouver le Big O d'une fonction récursive plongeante ?

Question

Je suis en train d'apprendre Big O et je suis bloqué sur un problème.

Problème -

int sample_function (int x) {
 if (x<1){
   return x;}

 int y = x/2; 
 return sample_function (y) + sample_function (x-y);
}

Quel sera le grand O si nous faisons 2 appels récursifs de (n/2) ? Je sais que le Big O d'une fonction récursive plongeante (n/2) est O(log(n)) mais je ne suis pas sûr de ce problème.

Answer 1

La solution de la relation de récurrence

T(n) = T(ceiling(n/2))+T(floor(n/2)) + O(1) 

es

T(n) = O(n).

Ceci peut être prouvé par induction sur n. La base inductive est simple. Comme pour l'étape d'induction, prenons c comme une constante positive telle que T(plafond(n/2)) et T(plancher(n/2)) sont bornés par c * plafond(n/2) et c * plancher(n/2), respectivement. Ainsi, la borne supérieure de T(n) est c * (plafond(n/2) + plancher(n/2)) = c * n.

Answer 2

Division d'un nombre entier x par 2 pour atteindre 0 prend environ log2(x) étapes. Chaque étape double le nombre d'appels de fonction. Par exemple :

  8
  4               4
  2       2       2       2
  1   1   1   1   1   1   1   1
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Au total, c'est sum( 2^k ), k = 0 ...log2(x) = O(x) .

Pour 0 et les négatifs que vous renvoyez lors du premier appel, c'est O(1) .

PS : On peut affirmer que la fonction est en fait O(1) . Un compilateur pourrait le remplacer par :

int sample_function (int x) {
    if (x < 1) return x;
    else return 0;
}

Answer 3

T(n) = 2 * T(n / 2) + O(1) = 4 * T(n / 4) + 2 * O(1) = 8 * T(n / 8) + 4 * O(1) = ... = n * O(1) + (n / 2) * O(1)

C'est donc O(n).