Est-ce que ces deux fonctions factorielles s'exécutent dans O (n)?

Question

La fonction récursive définie comme ceci:

function factrec($x) { 
    if($x <= 1) { 
     return $x; 
    } else { 
     return $x * factrec($x - 1); 
    } 
} 

Et itérative ici:

function factiter($x) { 
    $y = $x; 
    while($y > 1) { 
     $x *= ($y - 1); 
     $y--; 
    } 
    return $x; 
} 

J'avais lu que la fonction récursive du corps est O (1) et les appels récursifs O (n 1) en faisant O (n), mais pour l'itératif est-ce O (n) aussi?

Answer 1

Oui, les deux versions s'exécutent en heure O (n). Le raisonnement de la version itérative est fondamentalement le même que pour la version récursive: Le corps de la boucle s'exécute en O (1) fois et est exécuté n fois.

Cependant, il est à noter que la version itérative s'exécute dans l'espace O (1), tandis que la version récursive utilise l'espace de pile O (n) (car il y a une profondeur de récursivité de n).

Answer 2

oui c'est O (n). Essayez d'imaginer combien d'opérations le processeur exécutera lorsque vous avez une grande valeur de x. Avec de grandes valeurs, il ne devient pas plus complexe, et c'est toujours la même opération de manière linéaire.