Explication sur les fréquences

Bonjour à tous,

je suis tombé sur un algo pas très compliqué, mais j'ai du mal à comprendre l'explication de fréquence, voici l'ago:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public static int count(int[] a) { int n = a.length; int count = 0; for (int i = 0; i < n; i++) { 1] for (int j = i+1; j < n; j++) { 2] for (int k = j+1; k < n; k++) { 3] if (a[i] + a[j] + a[k] == 0) { count++; } } } } return count; }

---

et ils expliquent que les fréquences de calcul pour les 1], 2], 3] ème lignes sont:
1] N
2] N^2 / 2 - N/2
3] N^3/6 - N^2/2 + N/3


Je me demande pourquoi N^2 est divisé par 2, le N^3 par 6 et N par 3
Ensuite pourquoi c'est N^3/6 - N^2/2 et pas N^3/6 + N^2/2 alors que c'est +N/3 ?


Merci beaucoup :-)

Adrien

On va regarder le comptage qui donne N²/2-N/2

En fait, ce n'est pas vraiment une question d'algorithme, mais une question de maths.

Recherche 'Somme des n premiers entiers', et tu tomberas assez vite sur la formule S(n) = n(n+1)/2. Dans notre exercice, on ne calcule pas tout à fait la somme des n premiers entiers, mais la somme des n-1 premiers entiers. Ce qui donne (n-1)n/2, ou encore n²/2-n/2.

Et comment on tombe sur cette somme des n-1 premiers entiers ?
Quand i vaut 0, j prend toutes les valeurs entre 1 et n-1, donc n-1 valeurs possibbles.
Puis i vaut 1, j a alors n-2 valeurs possibles,
Et ainsi de suite.
Le nombre de passages dans cette boucle est donc (n-1)+(n-2)+ ... +2+1 : somme des n-1 premiers entiers.

Pour le second calcul, c'est un peu plus compliqué.

Bonjour :coucou:

Tu utilises 3 fois le mot "fréquence", mais je ne comprends pas ce que c'est. À mon avis, le terme est impropre.
De la même façon, j'imagine que le grand N de ton texte est le petit n de ton code.
Et la variable count n'a rien à voir avec la fonction count. :lefou: Joyeuses Pâques à tous.



Lorsque je lis le code, je vois un tableau d'entiers "a" et on tire 3 indices parmi N, pour faire la somme des valeurs du tableau à ces indices, indépendamment de l'ordre et sans répétition : c'est donc une combinaison.


Le reste, ce sont des simplifications.

Libre à toi de calculer les étapes intermédiaires en tirant 1 parmi N, et 2 parmi N.