Pourquoi

Dans CLRS (aux pages 49-50), quelle est la signification de l'énoncé suivant:

$\Sigma_{i=1}^{n} O(i)$ n'est qu'une seule fonction anonyme (de ), mais n'est pas la même chose que$i$$O(1)+O(2)+\cdots+O(n)$, qui n'a pas vraiment d'interprétation. "

Depuis $1+2+\dots+n =O(n^2)$, il est tentant de suggérer que $O(1)+O(2)+\dots+O(n) = O(n^2)$... mais ce n'est en fait pas valable. La raison en est qu'il peut y avoir une constante différente pour chaque terme dans la somme.

Un exemple

Laissez-moi vous donner un exemple. Considérez les sommes$S(1) = 1^2$, $S(2) = 1^2 + 2^2$, $S(3) = 1^2 + 2^2 + 3^2$, $S(4) = 1^2 + 2^2 + 3^2 + 4^2$, etc. Notez que$1^2 \in O(1)$, $2^2 \in O(2)$, $3^2 \in O(3)$, $4^2 \in O(4)$, et ainsi de suite pour chaque terme de la somme. Par conséquent, il serait raisonnable d'écrire$S(j)=1^2 + \dots + j^2$ sous la forme $S(j) = O(1) + \dots + O(j)$. Pouvons-nous donc conclure que$S(j) = O(j^2)$? Nan. En réalité,$S(n) = n(n+1)(2n+1)/6$, donc $S(n) = \Theta(n^3)$.

Si cela n'aide pas, essayons le développement mathématique plus précis suivant:

Une formalisation

Rappelons que l'interprétation de, disons, $O(n^2)$ c'est qu'il s'agit d'un ensemble de fonctions non négatives $f(n)$ (à savoir, l'ensemble des fonctions $f(n)$ de telle sorte qu'il existe des constantes $c \ge 0, d\ge 0$ tel que $f(n) \le c \cdot n^2$ pour tous $n\ge d$).

Au plus près nous pouvons arriver à une interprétation de $O(1) + O(2) + \dots + O(n)$ c'est que c'est l'ensemble des fonctions de la forme $f_1(n) + f_2(n) + \dots + f_n(n)$ tel que $f_1(n) \in O(1)$, $f_2(n) \in O(2)$, ..., $f_n(n) \in O(n)$.

Mais maintenant, les constantes pour chaque $f_i$peut être différent. Ainsi, chaque$f_i$ est une fonction non négative $f_i$ de telle sorte qu'il existe des constantes $c_i\ge 0,d_i \ge 0$ avec $f_i(n) \le c_i \cdot i$ pour tous $n \ge d_i$.

Maintenant, étant donné cela, que pouvons-nous dire $g(n) = f_1(n) + f_2(n) + \dots + f_n(n)$? Pas très utile. Nous savons qu'il existe une constante$d=\max(d_1,d_2,\dots,d_n)$ tel que $g(n) \le c_1 \cdot 1 + c_2 \cdot 2 + \dots + c_n \cdot n$ pour tous $n\ge d$. Maintenant, que pouvons-nous dire de cette somme? Eh bien, la réponse est que nous ne pouvons rien dire du tout. Il pourrait être arbitrairement important. Il est tentant de laisser$c=\max(c_1,c_2,\dots,c_n)$ et dis ça $g(n) \le c \cdot (1+2+\dots+n) \le c \cdot n^2 = O(n^2)$... mais ce n'est pas vraiment correct, car nous avons besoin d'une seule valeur constante de $c$ qui fonctionne pour tous $n$et la valeur $\max(c_1,c_2,\dots,c_n)$ est fonction de $n$, pas une constante.

Donc, il pourrait ne pas y avoir de constante $c$ tel que $g(n) \le c \cdot (1+2+\dots+n)$; il pourrait ne pas y avoir de constante$c$ tel que $g(n) \le c \cdot n^2$. Rien ne garantit que$g(n) \in O(n^2)$.

Pour plus de lecture

Voir https://math.stackexchange.com/q/86076/14578 et les termes Sums of Landau revisités pour d'autres questions qui traitent de ce problème général.

La raison pour laquelle le commentaire de CLRS prête à confusion est que, techniquement, $\sum_{i=1}^{n} O(i)$est défini comme$O(1) + O(2) + \ldots O(n)$. Ce qui se passe vraiment, c'est que CLRS abuse de la notation par souci de simplicité:

• $O(1)$représente un ensemble de fonctions. Il comprend, par exemple,$f(n)=1$, $f(n)=1/n$, et $f(n)=n^{1/n}$.
• Quand tu écris $O(1) + O(2)$ vous ajoutez techniquement deux ensembles $O(1)$ et $O(2)$avec une opération de somme . Lorsque cela est fait avec plus d'un nombre constant de termes, cela peut conduire à des comportements inattendus, comme l'explique clairement DW dans une autre réponse.

Au lieu de cela, le CLRS voudrait donc que vous interprétiez $\sum_{i=1}^n O(i)$ comme $\sum_{i=1}^n f(i)$ où la fonction générique $f(i) \in O(i)$. Par exemple, ils écriraient que$\sum_{i=1}^n 3i-5$ est $\sum_{i=1}^n O(i)$, ou $O(n^2)$.