¿Qué sale mal con las sumas de términos de Landau?

escribí

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

Pero mi amigo dice que esto está mal. De la hoja de trucos de TCS sé que la suma también se llama que tiene un crecimiento logarítmico en n . Entonces, mi límite no es muy agudo, pero es suficiente para el análisis que lo necesitaba.$H_n$$n$

¿Qué hice mal?

Editar : Mi amigo dice que con el mismo razonamiento, podemos demostrar que

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

¡Ahora esto obviamente está mal! ¿Que esta pasando aqui?

Lo que está haciendo es un abuso de notación muy conveniente.

Algunos pedantes dirán que lo que escribes no tiene sentido, ya que denota un conjunto y no puedes hacer operaciones aritméticas en ellos de la manera que lo estás haciendo.$\mathcal{O}(f)$

Pero es una buena idea ignorar a esos pedantes y asumir que representa a algún miembro del conjunto. Entonces, cuando decimos f ( n ) = g ( n ) + O ( n ) , lo que realmente queremos decir es que f ( n ) - g ( n ) ∈ O ( n ) . (Nota: algunos pedantes también pueden estremecerse ante esta afirmación, alegando que f ( n ) es un número $\mathcal{O}(f)$$f(n) = g(n) + \mathcal{O}(n)$$f(n) - g(n) \in \mathcal{O}(n)$$f(n)$$f$ es la función!)

Esto hace que sea muy conveniente escribir expresiones como

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

Lo que esto significa es que hay alguna de tal manera que$f \in \mathcal{O}(n^{1/3})$

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

En tu caso de

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

lo estás abusando aún más y debes tener cuidado.

Aquí hay dos posibles interpretaciones: ¿ refiere a una función de n , o una función de k ?$\mathcal{O}(1)$$n$$k$

Creo que la interpretación correcta es interpretarlo en función de .$k$

Si trata de pensarlo como una función de , aunque no sea incorrecto, podría conducir a posibles falacias, como pensar que k es O ( 1 ) y tratar de escribir ∑ 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 intenta pensar en ello como una función de , entonces es cierto que, si f = O ( g ) (como el argumento va a ∞ ) y g nunca es 0 , eso$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)|)$$

Tenga en cuenta que en el medio, hemos utilizado el abuso conveniente de la notación para significar que para alguna función h ∈ O ( g ) la suma es ∑ n k = 1 h ( k ) . Tenga en cuenta que la función final dentro de la O se refiere a una función de n . La prueba no es tan difícil, pero debe tener en cuenta el hecho de que se trata de un límite superior asintótico (es decir, para argumentos suficientemente grandes), pero la suma comienza justo en 1 .$\mathcal{O}(g(k))$$h \in \mathcal{O}(g)$$\sum_{k=1}^{n} h(k)$$\mathcal{O}$$n$$1$

Si intenta pensar en ello como una función de , entonces también es cierto que si f = O ( g ) (como el argumento va a ∞ ) entonces$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))$$

Entonces su prueba es esencialmente correcta, en cualquier interpretación.

Lo que escribiste es perfectamente correcto. El ésimo número armónico es de hecho en el conjunto de O ( n ) .$n$$O(n)$

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

El límite superior no es ajustado , pero es correcto.$O(n)$

$$i = O(1)$$

$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)$$

Sin embargo, lo correcto es usar la notación big-O solo al final. Límite superior de su suma tan apretada como sea posible, y solo cuando haya terminado use las anotaciones asintóticas para evitar estos escollos.