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

14

escribí

i=1n1i=i=1nO(1)=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.Hnn

¿Qué hice mal?

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

i=1ni=i=1nO(1)=O(n)

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

Rafael
fuente
2
Vea una discusión sobre las etiquetas de esta pregunta aquí .
Raphael
meta discusión sobre los algoritmos de etiquetas .
Kaveh
Vea también un tratamiento más concreto de un ejemplo común: ¿Cuál es el tiempo de ejecución asintótico de este bucle anidado?
Gilles 'SO- deja de ser malvado'

Respuestas:

10

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.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 yfO(f)f(n)=g(n)+O(n)f(n)g(n)O(n)f(n)F es la función!)

Esto hace que sea muy conveniente escribir expresiones como

nk=1nk1/kn+O(n1/3)

Lo que esto significa es que hay alguna de tal manera quefO(n1/3)

nk=1nk1/kn+f(n)

En tu caso de

k=1n1k=k=1nO(1)=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 ?O(1)nk

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 )nkO(1)k=1nk=k=1nO(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 , esokf=O(g)g0

S(n)=k=1nf(k)=k=1nO(g(k))=O(k=1n|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 .O(g(k))hO(g)k=1nh(k)On1

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 ) entoncesnf=O(g)

S(n)=k=1nf(k)=k=1nO(g(n))=O(ng(n))

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

Aryabhata
fuente
1
En pocas palabras: tenga en cuenta (asegúrese) que cada aparición de un símbolo de Landau introduce (tiene) su propia constante .
Raphael
8

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

Prueba: . i=1n1ilnn+12n=O(n)

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

JeffE
fuente
44
Bien: 1 / i ≤ 1 = O (1).
JeffE
1
La preocupación se dirige al segundo signo de igualdad. ¿Cómo verifico eso?
Raphael
2
Pero eso también es correcto. Una suma de n términos, cada uno de los cuales es O (1), es de hecho O (n).
Suresh
2
@Suresh Solo si las constantes implicadas por las s son independientes de la variable de suma, y ​​ese es el punto aquí (pregunta inicial). O
Raphael
2
iO(1)=O(n)i=O(1)
6

yo=O(1)

yonorteyo>norte/ /2yo=O(norte)i1n

i=1ni=i=1nO(n)=nO(n)=O(n2)

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.

Sonó.
fuente