1
votes

Comment puis-je calculer la fonction de temps T (n) du code suivant?

x=0;
for(int i=1 ; i<=n ; i++){
    for(int j=1 ; j<=n ; j++){
        x++;
        n--;
    }
}
By testing the code, the nested FOR loop recurs âŒˆn/2âŒ‰ times per steps of the first For loop.But I don't know how to formulate these rules with sigmas. I would really appreciate if anyone can help me with this.

algorithm data-structures time-complexity computer-science complexity-theory

3 commentaires

salut! Cette question peut être mieux adaptée pour CS StackExchange .

Pourquoi la boucle for imbriquée se répète ⌈n / 2⌉ fois par pas de la première boucle for si elles s'exécutent toutes les deux jusqu'à ce qu'elles atteignent n?

@Eloy Pérez Torres - Parce que la variable n décrémente à chaque étape de la première boucle.

3 Réponses :

1
votes

Vous pouvez exprimer T (n) comme T (n-2) +1, c'est-à-dire T (n) = T (n-2) +1 Ou sa complexité temporelle attendue est O (n / 2) => O (n).

Edit: L'expression T (n-2) +1 est évaluée comme vous pouvez voir si vous augmentez n-2 de 2 signifie que lorsque n-2 est devenu n, le nombre de fois que la boucle sera exécutée est le 1 + nombre de boucle temporelle exécuté pour n-2. 1 est dû au fait que vous incrémentez j et décrémentez n simultanément. c'est exactement la même chose que d'incrémenter j de 2.

2 commentaires

Comment avez-vous obtenu T(n-2)+1 ?

Je ne pense pas que ce serait la bonne réponse car nous ne décrémentons pas i et n simultanément. Chaque pas de la boucle externe divise n par 2.

0
votes

Dans la boucle interne, étant donné que n décrémente en même temps que j incrémente, n va être inférieur à j au milieu de la différence entre les deux valeurs initiales, soit (n-1)/2 . C'est pourquoi vos tests montrent que la boucle interne s'exécute « âŒˆn/2âŒ‰ fois par itération de la boucle externe.

Alors la boucle externe va s'arrêter lorsque pour le i qui satisfait cette égalité n/2^i = i-1 . Cela affecte la condition d'arrêt de la boucle externe.

n (1/2 + 1/4 + ... + 1/(2^i))

n/2 + n/4 + T(n/4)

n/2 + T(n/2)

T(n)

Cette série converge vers n sorte que l'algorithme est O(n) .

0 commentaires

1
votes

Calculons la valeur exacte de x .

TL; DR: x(N) = N-[N/2^i+1] , où i est le nombre le plus bas, satisfaisant la condition: (i+1) 2^i > N Comme Mariano Demarchi l'a dit, T(N)=O(N) .

Nous allons d'abord vérifier comment les variables changent après chaque boucle interne. Soit (n, i, x) valeurs entre 2 et 3 lignes de code (avant la boucle interne):

Combien d'itérations se produiront? Chaque itération augmente j et diminue n , donc la distance entre eux diminue de deux. La distance de départ est n-1 , et finale, après la boucle, est 0 (si n est impair) ou -1 (si n est pair). Ainsi si n=2k , la réponse est k , sinon k+1 . Ainsi, la boucle interne fait [(n+1)/2] = d itérations.
Ainsi x augmentera de d , n devient nd et i devient i+1 .
(n, i, x) -> (nd, i+1, x+d) ou égal ([n/2], i+1, x + [(n+1)/2])

Concentrez-vous maintenant sur les valeurs de n et i variables dans la grande boucle:

Ils changent comme ça: (n, i) -> ([n/2], i+1)
La condition d'arrêt est [N/2^i] < i+1 , qui est égal à (i+1)*2^i > N Bien sûr, nous avons besoin d'un i minimal, satisfaisant la condition.

Donc, i est le premier nombre satisfaisant la condition et nous NE SOMMES PAS davantage:

// finding i
unsigned long long i = 0;
while ((i + 1) * (1ll << i) < n)
    ++i;

// finding x
x = n - (n >> (i + 1));

Par la magie de la théorie des nombres (non liée à cette question) cette série est égale à N (1-1/2^i+1) . En particulier, si N est une puissance de 2 moins 1, nous pouvons le voir facilement.

Donc, ce code renvoie exactement la même valeur en temps O(log(N)) .

    x = [(N+1)/2] + [([N/2]+1)/2] + [([N/2^2]+1)/2] + ... + [([N/2^i-1]+1)/2]

0 commentaires