telescopica sucesion serie geometrica ejemplos divergente demostracion armonica alternada time-complexity big-o complexity-theory

time-complexity - sucesion - serie telescopica



Encontrando Big O de la serie armónica (3)

Pruebalo

1 + 1/2 + 1/3 + ... + 1/n is O(log n). Assume n = 2^k

Puse la serie en el resumen, pero no tengo idea de cómo abordar este problema. Cualquier ayuda es apreciada


Aquí hay una formulación usando Matemáticas Discretas:

Entonces, H (n) = O (log n)


Esto se desprende fácilmente de un hecho simple en Cálculo:

Y tenemos la siguiente desigualdad:

Aquí podemos concluir que S = 1 + 1/2 + ... + 1 / n es (log (n)) y O (log (n)), por lo tanto es Ɵ (log (n)), el atado es en realidad apretado.


Pregunta
1 + 1/2 + 1/3 + ... + 1 / n
Supongamos que n = 2 ^ k

  • Si el 3rd término es 1/3 y no 1/4 (1/2^2) , significa que hay n términos en todos, por lo que será O (n) . Es cierto que su suma puede ser log n , pero la complejidad es el número de iteraciones y no la suma de series.

  • Considera resolverlo programáticamente. Terminarías ejecutando el bucle 1 a n veces y agregando 1 / n a la suma. ¿Cuántas veces se ejecutó? 1 to n O (n)

  • Si el problema se cambió a 1 + 1/2 + 1/4 + ... + 1/n , la serie ahora se puede escribir como 1 + 1/2 + 1/4 + ... + 1/n ^ 2 + .. . + 1/2 ^ (k). Ahora la pista proporcionada por tu profesor también tiene sentido. ¿Cuántas veces se ejecutará el bucle? 0 to k = k + 1 times , y de ambas series podemos ver 2^k = n tanto k = log (n) . Entonces, la cantidad de veces que se ejecutó = log(n) + 1 = O(log n)

  • Supongo que usted o su profesor hicieron un error tipográfico.

Actualizar

Como señaló Dukeling, por supuesto, asumo que the provided function is pseudo-code and calculating the time complexity of that . Ahora, después de un año, entiendo por qué obtuve votos mixtos para esta respuesta en particular. Chicos, esto es y está destinado principalmente para la codificación. Si tiene problemas no relacionados directamente con la programación, debe usar un sitio de stackexchange diferente, como https://math.stackexchange.com/