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
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 es1/3
y no1/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 como1 + 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 ver2^k = n
tantok = 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/