Qu'est-ce qui ne va pas avec des sommes de termes Landau?

J'ai écrit

$\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

mais mon ami dit que c'est faux. De la feuille de triche TCS, je sais que la somme est également appelée qui a une croissance logarithmique en . Donc ma limite n'est pas très nette, mais est suffisante pour l'analyse dont j'avais besoin.$H_n$$n$

Qu'ai-je fait de mal?

Edit : Mon ami dit qu'avec le même raisonnement, nous pouvons prouver que

$\qquad \displaystyle \sum\limits_{i=1}^n i = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

Maintenant, c'est évidemment faux! Qu'est-ce qui se passe ici?

Ce que vous faites est un abus de notation très commode.

Certains pédants diront que ce que vous écrivez est un non-sens, car désigne un ensemble et vous ne pouvez pas effectuer d'opérations arithmétiques sur eux comme vous le faites.$\mathcal{O}(f)$

Mais c'est une bonne idée d'ignorer ces pédants et de supposer que représente un membre de l'ensemble. Donc, quand nous disons f ( n ) = g ( n ) + O ( n ) , ce que nous voulons vraiment dire si cela f ( n ) - g ( n ) ∈ O ( n ) . (Remarque: certains pédants pourraient également trembler à cette déclaration, affirmant que f ( n ) est un nombre et $\mathcal{O}(f)$$f(n) = g(n) + \mathcal{O}(n)$$f(n) - g(n) \in \mathcal{O}(n)$$f(n)$$f$ est la fonction!)

Cela rend très pratique l'écriture d'expressions comme

$$n \le \sum_{k=1}^n k^{1/k} \le n + \mathcal{O}(n^{1/3})$$

Cela signifie qu'il existe un certain de telle sorte que$f \in \mathcal{O}(n^{1/3})$

$$n \le \sum_{k=1}^n k^{1/k} \le n + f(n)$$

Dans votre cas de

$$\sum_{k=1}^{n} \frac{1}{k} = \sum_{k=1}^{n} \mathcal{O}(1) = \mathcal{O}(n)$$

vous en abusez encore plus et vous devez être prudent.

Il y a deux interprétations possibles ici: l' référence à une fonction de n , ou à une fonction de k ?$\mathcal{O}(1)$$n$$k$

Je crois que la bonne interprétation est de l'interpréter en fonction de .$k$

Si vous essayez de le penser en fonction de , pensé comme incorrect, cela pourrait conduire à des erreurs potentielles, comme penser que k est O ( 1 ) et essayer d'écrire ∑ n k = 1 k = ∑ n k = 1 O ( 1 $n$$k$$\mathcal{O}(1)$$\sum_{k=1}^{n} k = \sum_{k=1}^{n} \mathcal{O}(1)$

Si vous essayez de le considérer comme une fonction de , alors il est vrai que si f = O ( g ) (comme l'argument va à ∞ ) et que g n'est jamais 0 , cela$k$$f = \mathcal{O}(g)$$\infty$$g$$0$

$$S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(k)) = \mathcal{O}(\sum_{k=1}^{n} |g(k)|)$$

Notez qu'au milieu, nous avons utilisé l'abus commode de la notation pour signifier que pour une fonction h ∈ O ( g ) la somme est ∑ n k = 1 h ( k ) . Notez que la fonction finale à l'intérieur du O se réfère à une fonction de n . La preuve n'est pas si difficile, mais vous devez tenir compte du fait que vous avez affaire à une borne supérieure asymptotique (c'est-à-dire pour des arguments suffisamment grands), mais la somme commence juste à 1 .$\mathcal{O}(g(k))$$h \in \mathcal{O}(g)$$\sum_{k=1}^{n} h(k)$$\mathcal{O}$$n$$1$

Si vous essayez de le considérer comme une fonction de , alors il est également vrai que si f = O ( g ) (comme l'argument va à ∞ ) alors$n$$f = \mathcal{O}(g)$$\infty$

$$S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(n)) = \mathcal{O}(n g(n))$$

Votre preuve est donc essentiellement correcte, dans l'une ou l'autre interprétation.

Ce que vous avez écrit est parfaitement correct. Le ème nombre harmonique est en effet dans l'ensemble O ( n ) .$n$$O(n)$

Preuve: . $\sum_{i=1}^n \frac{1}{i} \le \ln n + 1 \le 2n = O(n)$$\square$

La limite supérieure n'est pas serrée , mais elle est correcte.$O(n)$

Pour le deuxième exemple, vous ne pouvez pas prétendre que

$$i = O(1)$$

puisque varie avec n . Après quelques étapes, il arrivera que i > n / 2 . Une manière plus appropriée consiste à dire que i = O ( n ) car en effet, tout au long de la sommation, i ne dépasse jamais 1 ⋅ n . Par ce raisonnement, n ∑ i = 1 i = n ∑ i = 1 O ( n ) = n O ( n ) = O $i$$n$$i>n/2$$i = O(n)$$i$$1\cdot n$

$$\sum_{i=1}^n i = \sum_{i=1}^n O(n)= nO(n) = O(n^2)$$

Cependant, la bonne chose à faire est d'utiliser la notation big-O uniquement à la fin. Limitez votre sommation aussi étroitement que possible, et uniquement lorsque vous avez terminé, utilisez les notations asymptotiques pour éviter ces pièges.