0
votes

Je ne comprends pas comment la 2e boucle a O (i ^ 2)?

La deuxième boucle passe de I à I ^ 2 -1 Donc non. de fois = i ^ 2 - i + 1 xxx

Exploitation extérieure N Times xxx

Ceci exécute J fois xxx

time-complexity

0 commentaires

3 Réponses :

0
votes

Vous trouverez votre réponse ici xxx

j est en cours d'exécution sur i ^ 2 (ou i * i), ce qui donne lieu à O (i ^ 2) pour la boucle interne

1 commentaires

Le point de départ peut être ignoré quand je deviens plus gros, tout comme un exemple, je prends i = 100 ... JJ Jour de 100 à 100 000, ce qui signifie 99,900 itérations qui sont presque à i * i.

0
votes

Donc non. de fois = i ^ 2 - i + 1
si i devient plus grand , par exemple extrêmement volumineux, alors i ^ 2 amd i est tous deux devenir extrêmement grand. Cependant, i ^ 2 augmente plus vite que i , puis l'augmentation de i peut être ignorée comparée à l'augmentation de i ^ 2 . Pour le Big-O notation de Complexité de temps , ceci est exprimé comme O (i ^ 2) . .
En plus, c'est "O" (lettre O), pas "0" (numéro zéro).

0 commentaires

0 votes Qu'est-ce que vous dites, c'est que parce que la boucle interne va de I à I², la complexité ne doit pas être O (I²). La complexité est en effet au plus O (i²) mais: pour i = 1 , la 2e boucle est exécutée 1 fois pour i = 10 , 90 fois (pas trop loin de 100) pour i = 100 , 9900 fois (pas trop loin de 10000) pour i = 1000 , 999 000 fois (pas trop loin de 1M) Chaque fois que vous multipliez I par un numéro N (10 dans mon cas), la boucle interne fonctionnera pour plus de N² plus de fois. Qui montre que la complexité est au moins o (i²). Conclusion: la complexité est exactement (= au plus + au moins) O (i²) Connaissances générales sur la complexité: La plupart du code que vous verrez jamais a une complexité de la liste ordonnée ci-dessous, ou une combinaison d'entre eux (plus à ce sujet plus tard): n ^ 0 (= constante) La complexité est un terme qui ne s'applique que pour des nombres très gros. Il n'est pas pertinent pour de petites valeurs, comme vous le verrez ici par exemple. Dans votre cas, avec une très grande valeur, i² est écrasant devant i donc o (i²-i) = O (i²) < / code>. Plus généralement, la complexité ne se multiplie que: Votre boucle extérieure est o (n) Votre boucle interne est O (n ^ 2) Résultat: votre échantillon de code est O (n ^ 3) Évidemment, lorsque vous combinez des complexités, la commande restera inchangée. Par exemple, ma liste ordonnée avant, multipliée par O (n) deviendra: n Comme vous pouvez le constater, grâce aux valeurs entre N et N ^ 2 dans ma liste précédente. 0 commentaires

Articles qui pourrait vous intéresser : Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Comment puis-je calculer la fonction de temps T (n) du code suivant? Ecrire une fonction pour F (n) = 0,5F (n-1) Laquelle de ces utilisations des fonctions ArrayToMap est la meilleure en termes de performances?