La complexité d'une fonction

Quel est le temps et la complexité spatiale de:La complexité d'une fonction

int superFactorial4(int n, int m) 
{ 
    if(n <= 1) 
    { 
     if(m <= 1) 
      return 1; 
     else 
      n = m -= 1; 
    } 

    return n*superFactorial4(n-1, m); 
}

Il fonctionne de manière récursive en diminuant la valeur de n par 1 jusqu'à ce qu'il est égal à 1, puis il soit diminuer la valeur de m par 1 ou renvoie 1 dans le cas où m est égal à 1.

Je pense que la complexité dépend à la fois de n et de m, peut-être que c'est O (n * m).

Source

2009-02-10 yyy

Ma tête est sur le point d'exploser. –

Cela ressemble à une tâche de devoirs pour moi. –

La complexité temporelle est O(n+m^2), la complexité de l'espace est la même.

Raisonnement: avec une valeur fixe de m, la fonction fait n appels récursifs à lui-même, chacun fait un travail constant, de sorte que la complexité des appels avec fixe m est n. Maintenant, quand n atteint zéro, il devient m-1 et m devient m-1 aussi. Donc, la prochaine phase-m fixe prendra m-1, le prochain m-2 et ainsi de suite. Donc, vous obtenez une somme (m-1)+(m-2)+...+1 qui est O(m^2).

La complexité de l'espace est égale, car pour chaque appel récursif, la récursivité prend de l'espace constant et vous ne revenez jamais de la récursivité sauf à la fin, et il n'y a pas de récursion de queue.

Source

2009-02-10 11:32:49 jpalecek

Je ne comprends pas: Je suis d'accord que pour une valeur fixe de m la fonction se fait n appels récursifs, mais quand n atteint 1, n et m sont diminués de 1 et la fonction se fera n-1 appels récursifs , donc la somme devrait être: (n-1) + (n-2) + ... + 1 qui est O (n^2) pour une valeur fixe de m, non? – yyy

Non, quand n atteint zéro, la ligne "n = m- = 1" a l'effet "m = m-1; n = m;" ce qui signifie que la valeur originale de n ne jouera aucun rôle dans le calcul ultérieur – jpalecek

En fait, il semble être plus proche de O (N + m^2) pour moi. n est seulement utilisé pour le premier "cycle".

En outre, dans tout langage qui ne fait pas l'optimisation de l'appel de fin, la complexité de l'espace est susceptible d'être "en échec". Dans les langages supportant l'optimisation, la complexité de l'espace est plus proche de O (1).

Source

2009-02-10 11:33:27 Darron

-1

La complexité temporelle d'une Factorielle avec récursion code pseudo:

int fact(n) 
{ 
    if(n==0) 
    { 
     return 1; 
    } 
    else if(n==1) 
    { 
     return 1; 
    } 
    else if 
    { 
     return n*f(n-1); 
    } 
} 

time complexity;  
let T(n) be the number of steps taken to compute fact(n). 


we know in each step F(n)= n*F(n-1)+C 

F(n-1)= (n-1)*F(n-2)+c 

substitute this in F(n), we get 

F(n)= n*(n-1)*F(n-2)+(n+1)c

en utilisant grande notation o maintenant on peut dire que

F(n)>= n*F(n-1) 
F(n)>= n*(n-1)*F(n-2) 
. 
. 
. 
. 
. 
F(n)>=n!F(n-k) 

T(n)>=n!T(n-k) 

n-k=1; 
k=n-1; 

T(n)>=n!T(n-(n-1)) 
T(n)>=n!T(1) 
since T(1)=1 
T(n)>=1*n!

maintenant il est sous forme de

Nous pouvons donc dire que la complexité temporelle de la factorisation en utilisant la récursivité est 01.

T(n)= O(n!)

Source

2011-09-23 14:42:06 kamal

La complexité d'une fonction

Répondre

Questions connexes