Complejidad Algorítmica

Claro, aquí tienes las notas de estudio del texto proporcionado:

Complejidad Algorítmica

• La complejidad se refiere a la cantidad de recursos, como tiempo o espacio, que un algoritmo necesita para completar su tarea en función del tamaño de la entrada.
• Complejidad temporal: Tiempo que tarda un algoritmo en completarse, en función del tamaño de la entrada.
• Complejidad espacial: Espacio de memoria que ocupa un algoritmo para completarse, en función del tamaño de la entrada.
• Generalmente, hay más interés en la complejidad de un algoritmo en cuanto al tiempo.

Medición de la Complejidad

• Interesa la complejidad asintótica, es decir, el tiempo que tarda para una entrada muy grande.
• No importa el tiempo exacto que tarda, sino cómo aumenta el tiempo a medida que aumenta el tamaño de la entrada.
• Se utiliza la notación Big O para representar la complejidad de un algoritmo.
• La notación Big O ignora las constantes y los términos de orden inferior.

Ejemplos de Notación Big O

• Dada una función $T(n) = 2n^3 + 5n^2 - n + 7$, donde n es el tamaño de la entrada.
• La notación Big O para este algoritmo es $O(n^3)$.

Complejidades Comunes

• $O(1)$: tiempo constante, el más rápido.
• $O(log n)$: tiempo logarítmico.
• $O(n)$: tiempo lineal.
• $O(n log n)$: tiempo linealítmico.
• $O(n^2)$: tiempo cuadrático.
• $O(n^3)$: tiempo cúbico.
• $O(2^n)$: tiempo exponencial.
• $O(n!)$: tiempo factorial, el más lento.

Consejos para Calcular la Complejidad

• Centrarse en el peor de los casos al calcular la complejidad de un algoritmo.
• Ignorar las constantes: $O(2n) = O(n)$.
• Ignorar los términos de orden inferior: $O(n^2 + n) = O(n^2)$.

Ejemplos en Python

Tiempo Constante $O(1)$

list = [1, 2, 3, 4, 5]
print(list)

• No importa el tamaño de la lista, esta operación siempre tomará la misma cantidad de tiempo.

Tiempo Lineal $O(n)$

list = [1, 2, 3, 4, 5]
for element in list:
    print(element)

• A medida que crece la lista, el tiempo necesario para completar esta operación crece linealmente.

Tiempo Cuadrático $O(n^2)$

list = [1, 2, 3, 4, 5]
for i in list:
    for j in list:
        print(i, j)

• A medida que crece la lista, el tiempo necesario para completar esta operación crece cuadráticamente.

Tensiones

• La tensión es la fuerza ejercida por un hilo, cuerda, cable o elemento similar sobre un objeto al que está atado.
• La tensión es una fuerza de "tracción", dirigida a lo largo del hilo y en dirección opuesta al objeto.

Ejemplo de Tensión

• Una lámpara colgante del techo.
• La lámpara está atada al techo por un cable.
• La tensión en el cable es igual al peso de la lámpara.

Cálculo de la Tensión

• La tensión se calcula utilizando la fórmula: $T = mg + ma$
  • $T$ es la tensión en el hilo
  • $m$ es la masa del objeto
  • $g$ es la aceleración debida a la gravedad ($9.8 m/s^2$)
  • $a$ es la aceleración del objeto

Ejemplo de Cálculo

• Calcular la tensión en un cable que sostiene un peso de 10 kg y se mueve hacia arriba con aceleración de $2 m/s^2$.
• $T = (10 kg)(9.8 m/s^2) + (10 kg)(2 m/s^2) = 98 N + 20 N = 118 N$

Diagrama de Cuerpo Libre

• Es una representación gráfica de las fuerzas que actúan sobre un objeto.
• Pasos para dibujar un diagrama de cuerpo libre:
  • Dibujar un diagrama del objeto
  • Dibujar todas las fuerzas que actúan sobre el objeto como vectores
  • Asegurarse de que la longitud de cada vector sea proporcional a la magnitud de la fuerza
  • Etiquetar cada vector con el nombre de la fuerza

Ejemplo de Diagrama de Cuerpo Libre

• Una lámpara colgante del techo está sujeta a dos fuerzas:
  • La fuerza de la gravedad, que tira de la lámpara hacia abajo.
  • La tensión en el cable, que tira de la lámpara hacia arriba.

Tabla de Fuerzas en el Diagrama

• En el diagrama, la fuerza de la gravedad se representa mediante un vector que apunta hacia abajo y la tensión en el cable se representa mediante un vector que apunta hacia arriba.
• La longitud de los dos vectores es la misma, ya que las dos fuerzas son iguales en magnitud.

Recomendaciones Adicionales

• La tensión es una fuerza que siempre está presente cuando un objeto está atado a un hilo, cuerda o cable.
• Un diagrama de cuerpo libre es una herramienta útil para analizar las fuerzas que actúan sobre un objeto.