Σ de i = 1 à n de (n) (n + 1)/2Quelle est la somme d'une somme?
Quelle est la limite supérieure de calcul pour un n? Est-ce O (n^3) O (n^2)?
Exemple:
n=1 , sum =1
n=2 , sum= 1+ 1+2 , sum = 4
n=3, sum= 1+1+2+1+2+3, sum = 10
n=4, sum = 1 + 1+2 + 1+2+3 + 1+2+3+4 = 20
n= 5, sum = 1+ 1+2 +1+2+3 +1+2+3+4 + 1+2+3+4+5 , sum = 35
...
n=10, sum = ..... , sum = 220
etc, alors quelle est la limite supérieure de ce calcul en fonction de N? est-ce:
O (n^3)?
Je suppose que vous voulez dire Σ 1 ≤ i ≤ ni ( i + 1)/2, puisque Σ 1 ≤ i ≤ nn ( n + 1)/2 est juste n ² ( n + 1)/2, que je suis sûr que vous auriez pu voir par vous-même. Quoi qu'il en soit, pourquoi devriez-vous supporter de simples taux de croissance asymptotiques quand vous pouvez calculer la somme exactement?
Σ 1 ≤ i ≤ ni ( i + 1)/2
= ½ Σ 1 ≤ i ≤ n (i ² + i)
= ½ (n ( n + 1) (2 n + 1)/6 + n ( n + 1)/2)
= n ³/6 + n ²/2 + n /3
le OEIS appelle ces numéros (1, 4, 10, 20, ...) le "tetrahedral numbers ".
C'est O (n^3).
Pour voir que cela est vrai, vous pouvez le visualiser comme une pyramide triangulaire.
Nous pouvons rapprocher n(n+1)/2-n^2. Donc, notre somme est 1^2 + 2^2 + ... + n^2, et c'est n(n+1)(2n+1)/6, ce qui peut être approximativement de n^3. Donc, la limite supérieure est n^3.
Oui, en sommant un polynôme de degré d sur k = 1,2, ..., n donne un polynôme en n de degré d + 1. Puisque k(k+1)/2 est de degré 2 en k, sa somme est de degré 2 + 1 = 3 en n.
La formule exacte de la somme est 1/6*n*(n+1)*(n+2), soit O(n^3).
Demandez-vous la complexité de calcul de la somme suivante, ou pour le grand-O lié pour la somme?
La seconde est O (n^3), comme les gens déjà remarqué, mais pour calculer la somme que vous avez besoin seulement d'une quantité linéaire d'additions et de multiplications. Vous pouvez regrouper les opérandes et réécrire la somme comme
n*1 + (n-1)*2 + ... + 1*n
d'où il est clair que la somme peut être calculé en O (n).
Oh, et Gareth noter qu'il y a expression de forme fermée pour la somme, qui calcule en temps constant.
Approximativement en intégrant un polynôme de grade 2 (c'est-à-dire 'n²') et vous obtenez' n³'. – Dario
Lorsque n = 2, la somme est (1) + (1 + 2), ce que je fais 4 (pas 3). Bien que je ne sois pas un expert. –