Qu'est-ce que le Big O, limite supérieure de ce code

Question

Je suis un peu confus, j'ai fait des recherches sur la complexité du temps Big O pendant quelques heures maintenant et lire tous les articles ici.

int myfunc(int n) 
{ int result = 0; 
    for (int i = 0; i<n; i++) 
    for (int j = i; j>0; j--) 
     if (i%j == 0) 
     result += j; 
    return result; 
} 

J'ai reçu ce code et je souhaite trouver la limite supérieure de ce code. Maintenant, d'après ce que j'ai appris jusqu'à présent, je suppose que la limite supérieure est O (n^2) parce que c'est une boucle imbriquée. Cependant parce que J est lié à I; Je me demande si ce code est réellement O (n log n), je dois dire que je ne comprends pas complètement le concept de O (n log n). Cependant, je comprends toutes les autres notations telles que ... O (1), O (n), O (log n), O (n^2), O (n!).

Answer 1

Pour chaque itération de la boucle externe, la boucle interne exactement i fois.

Lorsque i = 0, la boucle interne s'exécute 0 fois.

Lorsque i = 1, la boucle interne s'exécute 1 fois.

Lorsque i = 2, la boucle interne s'exécute 2 fois.

...

Lorsque i = n-1, la boucle interne exécute n-1 fois. Ainsi, le nombre total de fois que la boucle interne s'exécute = 0 + 1 + 2 + ... + (n-1) = (n * (n-1))/2 = (n^2 - n)/2.

Par conséquent, le nombre total de calculs impliqués = (n^2 - n)/2.

Ainsi, le temps complexité du code donné = O (n^2).

Answer 2

La réponse est O (n^2). Imaginez que la variable i soit le numéro de ligne d'une matrice et j le numéro de colonne. En utilisant cette boucle, vous ne regardez que la moitié de la matrice. Cela vous donne une complexité temporelle de O (0.5n^2), mais c'est juste O (n^2).

Pour essayer de vous aider à comprendre O (n log (n)):

Un exemple d'un O (log (n)) algorithme de complexité est une recherche binaire sur une liste triée des numéros. Vous définissez la moitié du problème à chaque comparaison en vérifiant l'élément du milieu et en éliminant la moitié de la liste qui est clairement au-dessus ou en dessous du nombre que vous regardez.

Faire cette même recherche binaire sur n ensembles différents de longueur n aurait une complexité temporelle O (n log (n)).

Answer 3

La boucle interne démarre itérations i fois, et i augmente de 1 contrôlée par la boucle externe.

Par conséquent, la boucle intérieure recevra 1, 2, 3, ..., n par la boucle extérieure et itérer, ce qui revient à la boucle intérieure itérer 1 + 2 + 3 + ... + n = n(n+1)/2

n(n+1)/2 = (n^2)/2 + n/2. La croissance de cette fonction est dominée par n^2 donc la limite supérieure peut être dit comme O(n^2).

Vérifiez les simulations que je viens de lancer.